Sign in to follow this  

a* path planning in several layers

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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.

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this