A couple of questions about pathfinding

I'm currently working on an isometric city sim game. Progress has been good - I'm at the stage where the user can put down buildings, and citizens will move from one building to another whilst avoiding obstacles in-between through use of the pathfinding behavior. I'm currently recalculating the pathfinding obstacle map for each citizen when a new building is placed. This works fine with a small number of citizens but, not surprisingly, it causes a stutter as the population grows (even less surprisingly, this stutter is most notable on mobile platforms). Aside from this, the framerate is consistent and high. My questions are:

Since all citizens use an identical obstacle map, is there a way of calculating the map once, then applying it to all entities?

Is there a way of adjusting individual collision map cells, rather than using the in-built "add object"/"re-calculate" functions?

I suppose if there's no obvious solution I could write my own pathfinding functions, but it would be a shame to not make use of this in-built feature.

Since all citizens use an identical obstacle map, is there a way of calculating the map once, then applying it to all entities?

When a path is found, you can access the X and Y coordinates of each node in the path using expressions. I don't know of any way to assign that same path to the "move along path" action, but you can use your own movement system to follow the path. Here's an example I made for someone else, but it should work for you too. The 2nd grouping in the capx is the one you're interested in because it saves the path to an array, which can then be used by other objects.

Demo

Capx

Is there a way of adjusting individual collision map cells, rather than using the in-built "add object"/"re-calculate" functions?

How exactly would you want to adjust them? I'm guessing you're looking to be able to specify a specific cell, and either change whether it contains an obstacle, or have it recalculate to check if it contains an obstacle. If so, I don't believe there is a way to do this.

That's not a bad solution. Unfortunately in my case the citizens all have completely unrelated paths, so using a common array of nodes wouldn't work. However, I could extend on your idea by making a single obstacle-map-calculating object that works out unique paths for any citizen upon request, then parses the node data back to the citizens to be stored locally (or an enormous array for every citizen's every node). The only downside of this method would be that only one path could be calculated at a time, so I would probably have to set up a queue in case two citizens try to calculate a path simultaneously. I have no idea whether this would be efficient on a large-scale, but it would solve my initial stuttering problem. I'll give this a shot if I can't find a better solution. Thanks for the idea and capx.

How exactly would you want to adjust them? I'm guessing you're looking to be able to specify a specific cell, and either change whether it contains an obstacle, or have it recalculate to check if it contains an obstacle. If so, I don't believe there is a way to do this.

Oh, I have no idea on the "how". I just figured that a "make this cell an obstacle" function would be hugely more efficient than the current "make this object an obstacle then recalculate" method.

I'll add direct cell manipulation to the todo list.

That's fantastic. Thanks a lot Ashley.

Hey Ashley, would be possible to add a "Load JSON Array as Obstacle Map"?

Animmaniac: I can add that to the todo list, but what's the use case?

Animmaniac: if direct cell manipulation were implemented, you could probably make a work-around by importing the JSON data into an array, then parsing the array data to the obstacle map with a couple of loops.

Ashley

When using tile based levels I often use an array to define obstacles, so it would be handy to easily import the preexisting array instead of generate it again.

It would also make easier to define our own generation map algorithms without depending on objects placed on the layout.

It's a speculation from my part, but I guess that the algorithm to calculate the obstacle map from polygonal, unaligned, rotated objects, that tracks partially covered cells, can be a lot more costly than manipulating the array directly. So maybe it's possible to have a world that updates much more frequently without impacting so much on performance.

Anyway, an integrated way to communicate with the array object would be useful. Of course if direct cell manipulation is added you can iterate through the array and update every cell like SketchyLogic said, but an JSON load would be pretty handy.