I've taken a look at a bunch of libraries with A* implementation, but they all seem to be grid based. I'd like to know the best way to go about implementing A* for non-grid based applications, where it checks also for physics objects to avoid.
[editline]8th March 2012[/editline]
If the solution is to do code it from scratch, I will. I'm just trying to save some time.
It doesn't matter if it is on a grid or a node tree type thing. The grid squares are simply nodes. Of course if you have unevenly spaced nodes, you will need to weight them accordingly. No idea what libs you've looked at or what is available really. Implement it yourself as a learning exercise :)
When you have a grid, each node has 4 neighbours (or 8 if you can also travel diagonally): right, up, left, down. The cost of travelling to these nodes (assuming they are all the same type (e.g: grass) and elevation) is exactly the same, because the distance is uniform.
Such a setup is just a perfect case of a spatial system. When working with a less-than-perfect environment, you simply define the nodes and their connections yourself.
The algorithm just has to have a different neighbour iteration method, that is: instead of going "right, up, left, down".. you go "neighbour 1", "neighbour 2", "neighbour 3", and so on.
For the cost of travelling to that neighbour, you use the distance.
This isn't a big change, and you should be able to use your existing code.
[QUOTE=Deco Da Man;35048316]When you have a grid, each node has 4 neighbours (or 8 if you can also travel diagonally): right, up, left, down. The cost of travelling to these nodes (assuming they are all the same type (e.g: grass) and elevation) is exactly the same, because the distance is uniform.
Such a setup is just a perfect case of a spatial system. When working with a less-than-perfect environment, you simply define the nodes and their connections yourself.
The algorithm just has to have a different neighbour iteration method, that is: instead of going "right, up, left, down".. you go "neighbour 1", "neighbour 2", "neighbour 3", and so on.
For the cost of travelling to that neighbour, you use the distance.
This isn't a big change, and you should be able to use your existing code.[/QUOTE]
But what if you're working in a dynamic 2d enviroment?
What if you want the game to dynamically plot out nodes without you having to do anything? (No lazy PRM)
What if there are tiny cracks but you still want your game to find a path through that?
[QUOTE=AtomiCasd;35048702]But what if you're working in a dynamic 2d enviroment?
What if you want the game to dynamically plot out nodes without you having to do anything? (No lazy PRM)
What if there are tiny cracks but you still want your game to find a path through that?[/QUOTE]
In this situation A* probably isn't the best solution. You could overlay a grid over the map at run-time and figure out if each node is traversable or not. But for something like this Dijkstra's would probably be best.
I don't get why people have so much trouble with "non-grid-based" A*.
It totally absolutely has nothing to do with grids whatsoever. If you find a proper description of the algorithm, they won't even mention grids.
[QUOTE=AtomiCasd;35048702]But what if you're working in a dynamic 2d enviroment?
What if you want the game to dynamically plot out nodes without you having to do anything? (No lazy PRM)
What if there are tiny cracks but you still want your game to find a path through that?[/QUOTE]
The neighbors of a node can be generated at algorithm run-time. For instance, you could have nodes generated by selecting 8 offsets in a circle around the current node. If a spot isn't traversible from the current position, then it's culled, resulting in a final set of possible nodes to check.
There's no rule that you have to have a constant, unchanging graph. Obviously you might run into problems by doing this however; a player could maybe close and open a door over and over, causing the enemy to just run back forth down a hallway indefinitely.
I'm actually of the opinion that A*, or really any of the graph traversal algorithms that were made for practical problems like flight scheduling, are not generally the best option for a game. Because in a game, you use pathfinding for AI, which just results in an AI that, unrealistically (and un...fun-ly), can find it's way through a complex maze on the first try.
An AI is, in most cases, supposed to be a entity that acts in a believable, human, fashion. Knowing the entire world as a node graph, and being able to pathfind the shortest path between any two points isn't natural, it isn't human.
If you're looking for a relatively-ready-to-go AI solution there's this:
[url]http://code.google.com/p/recastnavigation/[/url]
Provides both navmesh generation and pathfinding through said nav-meshes. Written by an Ex-Crytek AI programmer, free for use in everything.
[QUOTE=ROBO_DONUT;35050761]I don't get why people have so much trouble with "non-grid-based" A*.
It totally absolutely has nothing to do with grids whatsoever. If you find a proper description of the algorithm, they won't even mention grids.[/QUOTE]
because lots of people have no understanding of the underlying concepts - only specific applications of those concepts
[QUOTE=AaRoNg11;35049632]In this situation A* probably isn't the best solution. You could overlay a grid over the map at run-time and figure out if each node is traversable or not. But for something like this Dijkstra's would probably be best.[/QUOTE]
Bad advice. Dijkstra's is always worse.
[QUOTE=Smashmaster;35055750]Bad advice. Dijkstra's is always worse.[/QUOTE]
If you have a "shortcut" (e.g: a portal) that lays in the opposite direction to the target, Dijkstra's lack of a heuristic means it will be found; whereas A* may miss it.
[QUOTE=Deco Da Man;35057772]If you have a "shortcut" (e.g: a portal) that lays in the opposite direction to the target, Dijkstra's lack of a heuristic means it will be found; whereas A* may miss it.[/QUOTE]
It all depends on the heuristic itself.
Sorry, you need to Log In to post a reply to this thread.
