# a* path planning in several layers

This topic is 4903 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

i'm dealing with a game similar to gta1 / gta2, the city is a huge array of blocks in several layers, the start and goal can be at different layers, what variant of A* do you recommend for such situations? solving would include this include finding safe bridges over roads, etc basicly it has to work fast, not that accurate.

##### Share on other sites
I'm pretty sure that they have several layers of pathfinding (macro...micro).
Example:
The highest layer is where you get a straight line from the starting point to the destination. Then it goes deeper and deeper down until it reaches micro, where it basically avoids obstacles like trashcans, pedestrians and stuff like that.
In one of those layers, you could take care of the virtual, physical problem, where the bridges, buildings etc. are placed to also take them into account.
That way you won't bother to find out the best way to avoid trashcans on different layers in a early stage of the pathfinding.
The bridges would be a much higher layer in parthfinding than trashcans, but also lower than the general way to get from point A to point B.
Maybe it should first figure out a inaccurate rute, and thereafter check whether it needs to be computed in different layers.
I'm not totally sure on my theory since I haven't done anything this extensive yet, but I'm pretty sure it would work faster than a single layered A*.

##### Share on other sites
A* works with several layers. A graph and a non-optimal heuristic for extra speed, if indeed necessary, and that's it.

##### Share on other sites
While xor's response is rather terse, it is also correct. A* does not require that the search be conducted on a regular grid of any number of dimensions. Indeed, all tree-based search algorithms can be applied to any graph structure (and here, by graph, I mean the construct G = < V,E >, where V is a set of vertices (nodes) and E a set of edges that connect the vertices). The topology of the graph is irrelavent to the search algorithm.

The only problem one typically faces in constructing a graph to represent a search problem is correctly translating the properties of the environment into a reasonable set of nodes and edges. Since the search problem is solved with respect to the graph (and not the domain) then one requires that the graph is an accurate representation of the domain if one is to assume that the plan (path) found is useable in the domain.

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 9
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009391
• ### Who's Online (See full list)

There are no registered users currently online

×