Hi, I am doing a tile-based game at the moment, and I have a question regarding pathfinding over large distances. The world of this game consists of multiple sectors, which contain the actual tile maps. So if you leave sector (1,1) over the bottom border line, you enter (1,2). I want the entities in this world to be able to find a certain point in other sectors. Let's say there is a shop in (1,3) and the entity in (1,1) decides it wants to buy something. I have limited the iterations of A* to 10k because otherwise it becomes a real power hog (it is a single function that tries to return a path immediately). Might a thread-based or step-based A*-algorithm be good here, so the entity will pause until it has found a proper path? What other options are there if the entity does not find a way to the shop on first attempt? I have been thinking about pre-generated path nodes, but all maps are randomly generated. Might be tricky to implement sensible path node placement. Any other ideas?

Does your algorithm path from sector to sector first? If not, that would be a great place to start. Paths crossing a sector can be precalculated at the time of map generation, or cached after first use.

I don't know what you mean by 'first attempt' as A* doesn't really have the notion of attempts. Perhaps you mean the situation where you have moved A* to the background and it is taking too long to return a path - in that case, you might consider giving the entity a provisional path, eg. a straight line towards the goal.

Normally this sounds like a problem for dynamic programming, but building a graph and planning using A* shouldn't be that problematic in terms of speed either.

You could revert to do local planning instead of a global planning. I'll see if I find a a good link, "dynamic window approach" would be a name. This is used sometimes when planning on mobile robots with limited cpu power.

How many nodes are in each sector? I'm assuming that's where your problem is.

If that is the case, doing a hierarchical pathfind is the best bet. For example, if you know that you can get from the entrance to 1,1 to the exit to 1,3 in 1,2, then you don't really care how you traverse 1,2... you just know that you need to move through there.

Think of how you move through your house. You go from room to room... and only when you are in a room do you care about how to get across the room. Or when you plan a trip, you think about connecting cites in order. When you are in a city, you worry about how you get around in that city. But it doesn't matter until you get there.

For each sector you may be able to identify 'portals' between the sectors so that you could use center points of the portals as the waypoints instead of the center of the sector itself. The second tier (fine) pathfinding would be to traverse a sector (portal to portal) and more realistic paths would be built between these entry/exit portals for each sector along the coarse path (first and last being the exceptions).

In town scapes (or buildings with many small rooms/doorways) the portals exist (versus a more open terrain with few/no movement blocking obstacles).

You do can make a program analyse/identify the portals (OR you can designate them by hand...)

Quote: Original post by wodinoneeye
For each sector you may be able to identify 'portals' between the sectors so that you could use center points of the portals as the waypoints instead of the center of the sector itself. The second tier (fine) pathfinding would be to traverse a sector (portal to portal) and more realistic paths would be built between these entry/exit portals for each sector along the coarse path (first and last being the exceptions).

In town scapes (or buildings with many small rooms/doorways) the portals exist (versus a more open terrain with few/no movement blocking obstacles).

You do can make a program analyse/identify the portals (OR you can designate them by hand...)

More on this, because I think it's interesting...

A very simple ("naive?") method for calculating "portals" or "chokepoints " is as follows:
1. Start with an array full of zeros (corresponding to your pathfinding nodes)
2. Pick two points at random and compute the shortest path between them.
3. Add 1 to all elements in your array on this path.
4. Repeat 1-3 for a bunch of trials
5. Chokepoints are now the maxima in your array

It's not without its problems, however. For instance, if almost all of your area is in two islands, and those islands are connected by two bridges, one very long and the other very short, then the short bridge will be identified as a chokepoint but probably not the long bridge, even though it is.

So, let's look at another method: The Visibility Graph. This is provably optimal when your distance metric is Euclidean distance, in that it always finds a shortest path. In a world with polygonal obstacles, what you should do is pathfind over the graph whose vertices are 1. the start vertex, 2. the goal vertex, 3. all of the polygon vertices, where two vertices are connected by an edge iff they can "see" each other (i.e., the line segment joining them intersects nothing). Since your map is "cells," you'd have to trace around obstacles (see another poster's questions about contour tracing in this forum), and whenever you'd run into a "corner" you'd need to add a vertex. You could also "smooth" these outlines to reduce the number of vertices, of course.

Also, here's another, completely different thought, which I'm sort of making up right now on the spot, but not completely, because it's related to a labmate's research: What if you compute an approximate Voronoi partition of your map, and then use the vertices of the graph thereby generated for your pathfinding?

Basically, for every point on your grid, compute the distance to the nearest obstacle (there are reasonably efficient ways to do this by starting a flood-fill at obstacle boundaries and working out). Then, you'll see that there are "maxima" on your grid -- places that are further away from all obstacles than any others. In addition, there will be "valleys" in this function exactly halfway in between obstacles, and these "valleys" will connect the "maxima." These "valleys" become edges of a graph; they connect vertices which are the "maxima."

So, you could compute a path from your start to the nearest Voronoi vertex, and a path from your goal to its nearest Voronoi vertex (both small problems, presumably), and then compute a path between the Voronoi vertices on the simplified Voronoi graph. This path would be close to optimal, but it might be a little strange at the beginning and the end, since it might, e.g., "go backwards" in order to get onto the "onramps" for the Voronoi "highway." A way to deal with this would be to add a postprocessing "relaxation" step -- physically, this would be analogous to pretending that your path was a rubber band and stretching it taut.

This method has the advantage over the visibility graph method that it would presumably pathfind on a much, much smaller graph. Also, intuitively, after you performed relaxation, I think you would get optimal paths (though I have not proven this). So this might be something to seriously consider, actually.