7
\$\begingroup\$

I have a large 2d tilemap, ranging anywhere from hundreds to thousands in size. The map is formed by 8x8 chunks. I am currently using A* but it isn't quite efficient because I may have as many as a hundred objects pathfinding simultaneously. The path doesn't have to be the absolute shortest, but a certain degree of shortness is expected.

I've looked here and saw that HPA* might work for me since my map is broken into smaller chunks. However, because the map is highly dynamic (let's assume that at least two chunks are modified per second) it seems there may be better alternatives.

Also, D*/Lite (mentioned in the link) might work, but how can it be optimized for a chunk based grid?

My question isn't particularly about HPA* or D*, but rather about finding an optimal algorithm for a large and dynamic, chunk-based, tilemap.

EDIT: The chunks contain procedurally generated content. Most of the time this will mean that the chunk is empty except for about 10-20% of its tiles, however sometimes this number can go up to 90% (that is in the case of generated "blobs"). The chunks will contain near-arbitrary data, and two chunks will rarely be the same.

Furthermore, each agent will have an independent path, however because the map is dynamic, it may contain man-made corridors and long passage ways that might result in them being shared often by many agents.

Most goals will be arbitrarily located, however there will be some predefined goals (locations) as well. For those predefined locations, I am considering using a vector field (sort of like a heat map) that can be used to approach it. However, doing this for every goal would be terribly inefficient especially since I would use the generated field only once (or in better cases, maybe a few times).

\$\endgroup\$
  • 1
    \$\begingroup\$ Can you give us some details about what these chunks are like? Are they chosen from a fixed pool, or could they have arbitrary contents? Example images are always helpful for questions with a geometric component. :) Also, what kind of pathfinding do you need? Is every agent using an independent goal/path, or is there any degree of swarming or shared goals? \$\endgroup\$ – DMGregory May 27 '17 at 15:46
  • \$\begingroup\$ @DMGregory I have explained the specific details. :) \$\endgroup\$ – Dave May 27 '17 at 15:58
  • \$\begingroup\$ I will suggest looking into Jump Point Search which is a fantastic optimization on A* as it reduces the number of nodes needed to search by eliminating expansion directions that couldn't possibly be optimal. \$\endgroup\$ – Draco18s May 27 '17 at 16:36
  • \$\begingroup\$ @Draco18s Interesting, that could be very helpful for the corridors! Thanks for the tip. \$\endgroup\$ – Dave May 27 '17 at 16:59
  • 1
    \$\begingroup\$ @BlueRaja-DannyPflughoeft Unique \$\endgroup\$ – Dave May 27 '17 at 18:07
2
\$\begingroup\$

Hundred objects doing pathfinding constitutes a "crowd" I think. For this, you should look into Continuum Crowds by University of Washington.

What you do, is solve the pathfinding from anywhere on the map, to a goal. Then every agent that shares that goal can use it.

This works well if you have many agents, but only a few different goals.

I've used this in my pyramid building sim which can do thousands of agents doing pathfinding at 60Hz.

It comes down to solving for the entire map: what is the distance from here to the goal. From that map, calculate a gradient, and follow that gradient.

It comes with some nifty features, as "automatic lane forming" if two streams (with different goals) collide with each other. The agents will then form lanes, as moving against the predominant flow is more expensive than going with it.

The image below shows this "potential field" (distance to a particular goal) visualized as a colour, and then a gradient vector field superimposed.

enter image description here

\$\endgroup\$
0
\$\begingroup\$

You likely do not want to run a full path-finding algorithm PER unit: this is probably where you're finding the inefficiency. Instead you would create a shortest-path-to-goal map per goal location. So if multiple units are headed to one goal, they would simply lookup in this map which tile is the next closest tile to move to.

Such a map would be a separate grid that's computed based on the main grid you're working with. But more than just walls, any "open" tiles would contain numbers that are precomputed as shortest distance to the goal from that spot.

An example computed map would look like (X denotes a wall, 0 denotes the goal)

6 5 4 3 2 3
7 X 3 2 1 2
8 X 2 1 0 1
X X X X X 2

Any unit headed towards the goal (the 0) would simply follow the numbers in this grid downwards. Any change to the grid would force you to recompute this map (and how you make this efficient depends on your particular algorithm). A simple approach to create such a map would be to use a a Breadth First traversal from the goal location.

The main idea is that you can have hundreds of units using the same path map to find their way to a goal without computing a separate path for each of them.

\$\endgroup\$
  • \$\begingroup\$ This will work if there are only a few endpoints. It sounds like that is not the case, though his question isn't entirely clear. \$\endgroup\$ – BlueRaja - Danny Pflughoeft May 27 '17 at 17:24
  • \$\begingroup\$ I have multiple end points, but these end points change frequently, so generating a heat map may not be the best choice. \$\endgroup\$ – Dave May 27 '17 at 18:08
  • \$\begingroup\$ You'll still likely want one heat map per end point, instead of running path-finding per unit (every time the goals change) If you have 1000 units and only 4/5 endpoints that change, you'll still want to generate this heatmap approach. If you run pathfinding per unit on each change, you're doing 1000*4/5 path-finding runs, instead of 4/5 heatmap updates. Your question would then become how would you modify a heatmap like this quickly? This is how it's done with any game where you have hundreds of units (either using tiles or waypoints) \$\endgroup\$ – Danny Yaroslavski May 27 '17 at 18:15
  • \$\begingroup\$ @DannyYaroslavski Yes I agree, but I've already said that I will do this for the predefined/less-often-changing points, in the body of the question. \$\endgroup\$ – Dave May 27 '17 at 18:17
  • \$\begingroup\$ I just don't understand why you'd be using the vector map only once- like I said, you'd have a vector map PER endpoint. If multiple units share the same endpoints, this is the ideal way to go about this. Otherwise if you have multiple units sharing the same dynamic map and not sharing endpoints, then yes, you would not be able to optimize anything. \$\endgroup\$ – Danny Yaroslavski May 27 '17 at 18:19
0
\$\begingroup\$

Since every unit has a unique endpoint, you best bet will likely be HPA*.

When a chunk changes, you'll need to update its node at every layer in the hierarchy, then rerun pathfinding on each unit (if a wall was added, you can skip units whose best-path didn't go through that node). Since the graph changes so often, I'd recommend only running the path-finding at the highest layer, then only drilling down when necessary. The top-layer has few nodes, so this will be super-fast.

At that point, profile. If you determine you need to make your pathfinding faster, you could look into things like JPS (for the bottom-most layers), DynamicSWSF-FP (for the higher layers), etc. You could also cache the most common queries at each layer. Another good optimization would be to only recalculate the path for some units each frame.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.