Pathfinding with nodes... finding the first node.
Is there any chance you can change the data structure containing the nodes to be more of a hash table or tree based on game space regions? Like hashing them out by room number or screen panel? Then you can just search for a starter node based on general region of the player.
Author
BCullus:
At this point, I'd adjust the data structure to anything that could possible work. I can put pointers to nodes into any imaginable format-- the only caveat is that since users create levels, it has to be able to generate the structure algorithmically, and it can't take *too* long.
See, my favored option would be to just make grid squares-- so if you fall within square[1][3], these are the only nodes that need to be checked against. The problem with it is, say I make the squares cover 100x100 pixels... what if a node is not straight line accessible from a series of control points (say, center of square, and each corner) but could be accessed from position 73,21 within the square? Meanwhile, testing every single pixel within the square would be time prohibitive. A further problem would be if a square is bisected by a line, so some nodes are accessible from one side, some only from the other.
The absolute perfect brute force solution-- which would be time and memory prohibitive-- would be to test each node from every pixel, and then merge pixels that end up with the same list of accessible nodes. That'd solve it all perfectly-- but would take a looooong time to generate.
So suggest away-- in fact, one could even say I'm looking for the magical data structure that makes this possible.
At this point, I'd adjust the data structure to anything that could possible work. I can put pointers to nodes into any imaginable format-- the only caveat is that since users create levels, it has to be able to generate the structure algorithmically, and it can't take *too* long.
See, my favored option would be to just make grid squares-- so if you fall within square[1][3], these are the only nodes that need to be checked against. The problem with it is, say I make the squares cover 100x100 pixels... what if a node is not straight line accessible from a series of control points (say, center of square, and each corner) but could be accessed from position 73,21 within the square? Meanwhile, testing every single pixel within the square would be time prohibitive. A further problem would be if a square is bisected by a line, so some nodes are accessible from one side, some only from the other.
The absolute perfect brute force solution-- which would be time and memory prohibitive-- would be to test each node from every pixel, and then merge pixels that end up with the same list of accessible nodes. That'd solve it all perfectly-- but would take a looooong time to generate.
So suggest away-- in fact, one could even say I'm looking for the magical data structure that makes this possible.
See, my favored option would be to just make grid squares-- so if you fall within square[1][3], these are the only nodes that need to be checked against.
Precisely what I was thinking, let's go with that.
what if a node is not straight line accessible from a series of control points (say, center of square, and each corner) but could be accessed from position 73,21 within the square?
Aren't you only interested in testing straight-line accessibility from the location of the pathfinding entity? Don't these entities know their world location (regardless of AI pathfinding nodes)?
Since A* is just a version of Djikstra's shortest path algorithm with a special heuristic, maybe you should start by implementing Dijkstra's algorithm? They both sort of work like a floodfill or breadth first algorithm, but the A* algorithm chooses the next node to explore "optimally", where optimal is a heuristic function that is up to you to decide (usually distance based).
What data structure are you using to store your nodes and edges? Is this search in 2-d space or 3-d space?
What data structure are you using to store your nodes and edges? Is this search in 2-d space or 3-d space?
This seems like a great case for a navigation mesh. Is there a particular reason you want to use a node-based solution instead?
Author
This seems like a great case for a navigation mesh. Is there a particular reason you want to use a node-based solution instead?
Only in terms of auto-generation. The game allows user created levels, where the user draws lines and circles that block off areas of the world. The navmesh would have to autogenerate based off that data, but I haven't been able to produce a method that generates a navmesh quickly and well.
Since A* is just a version of Djikstra's shortest path algorithm with a special heuristic, maybe you should start by implementing Dijkstra's algorithm? They both sort of work like a floodfill or breadth first algorithm, but the A* algorithm chooses the next node to explore "optimally", where optimal is a heuristic function that is up to you to decide (usually distance based).
What data structure are you using to store your nodes and edges? Is this search in 2-d space or 3-d space?
It's 2D-- flat surface, like a old Legend of Zelda game with an arbitrary world instead of a tiled world. I'll look up Dijkstra's.
Author
[quote name='JohnnyLightwave' timestamp='1354220555' post='5005435']
See, my favored option would be to just make grid squares-- so if you fall within square[1][3], these are the only nodes that need to be checked against.
Precisely what I was thinking, let's go with that.
Aren't you only interested in testing straight-line accessibility from the location of the pathfinding entity? Don't these entities know their world location (regardless of AI pathfinding nodes)?
[/quote]
The grid method turns out problematic-- especially when a grid is bisected by a line. It's possible that some points within the grid square can access this node and this node, whereas other points can't. Aside from checking every single pixel within the grid block (not speed feasible), there's no good way to correctly determine who should go in each grid's accessibility list. Since I'm doing user-generated levels, I can't do level design around the weaknesses.
Yes, the entities know their world location-- the issue is establishing an efficient data structure that can say "this location can access these nodes."
Aren't you only interested in testing straight-line accessibility from the location of the pathfinding entity? Don't these entities know their world location (regardless of AI pathfinding nodes)?
Yes, but here's my problem, and how it could miss cases...
Say I generate a node accessibility grid-- say it's 100,100. So to get a list of potentially accessible nodes, I just look at posx/100,posy/100 ... no problem so far.
Now, I'm generating accessibility. I'm working with, say, gridsquare[5][8]. I do this by picking some important points on the grid square (center, corners, maybe a few more)... so I have node 7, and I'm trying to see whether it goes into [5][8]'s list. I check center and corners, and nope, no accessibility. BUT: this is only so because of a quirk of the collisions-- there IS a point within that gridsquare that gives access to this node, but it's not the center or the corners. What I don't know how to figure is, how do I, without checking EVERY single spot within the grid square, notice that node?
In my experience, if I'm trying to generate an algorithm and it's proving mind-bogglingly difficult, it's usually that I've engineered the environment or approach in an inefficient manner to begin with. I.E. my "there's probably an easier way to be doing this" rule. It comes up a lot with my code.
I still don't see the reasoning for the corner/midpoint test. You mentioned your problem was with determining which node (a discrete list of objects) is closest to the entity that needs to begin pathfinding. So what's the purpose of your "accessibility list" for each square? Doesn't the algorithm run efficiently enough checking every node in a square? Something like:
Step 1: generate subset of node list(via grid-location) as "potentials" : nodes in grid[entityLoc % x][entityLoc % y]
Step 2: for each potential, can entity straight-line reach it? (*straight-line test assumes it detects if the straight line crosses any player-drawn walls)
If yes: mark as best option, check rest of list for closer option
If no: proceed with list
Step 3: If no best option was generated, expand "potentials" list to neighboring grid squares, repeat.
Am I over-simplifying the environment and/or missing some dynamic element thanks to player-generated content?
I still don't see the reasoning for the corner/midpoint test. You mentioned your problem was with determining which node (a discrete list of objects) is closest to the entity that needs to begin pathfinding. So what's the purpose of your "accessibility list" for each square? Doesn't the algorithm run efficiently enough checking every node in a square? Something like:
Step 1: generate subset of node list(via grid-location) as "potentials" : nodes in grid[entityLoc % x][entityLoc % y]
Step 2: for each potential, can entity straight-line reach it? (*straight-line test assumes it detects if the straight line crosses any player-drawn walls)
If yes: mark as best option, check rest of list for closer option
If no: proceed with list
Step 3: If no best option was generated, expand "potentials" list to neighboring grid squares, repeat.
Am I over-simplifying the environment and/or missing some dynamic element thanks to player-generated content?
hey im new , heres abit of psudo code of how a* works, it was given to me by my ai code ninja teacher at uni and really helped me to understand path finding
//-------------------------------------------------------------------------------------------------------
//1. Add the starting square (or node) to the open list.
//2. Repeat the following:
// a) Look for the lowest F cost square on the open list. We refer to this as the current square.
// b) Switch it to the closed list.
// c) For each of the 8 squares adjacent to this current square …
// * If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
// * If it isn't on the open list, add it to the open list. Make the current square the parent of this square.
// Record the F, G, and H costs of the square.
// * If it is on the open list already, check to see if this path to that square is better, using G cost as
// the measure. A lower G cost means that this is a better path. If so, change the parent of the square
// to the current square, and recalculate the G and F scores of the square. If you are keeping your open
// list sorted by F score, you may need to resort the list to account for the change.
//
// d) Stop when you:
// * Add the target square to the closed list, in which case the path has been found (see note below), or
// * Fail to find the target square, and the open list is empty. In this case, there is no path.
//3. Save the path. Working backwards from the target square, go from each square to its parent square until
// you reach the starting square. That is your path.
//-------------------------------------------------------------------------------------------------------
for some clarity
F is the shortest path, from node current
G is the goal
H is the cost to get from node current to node next,
heuristics are important to weight topographical changes in the pathfinding or dangers or impassable obsticles
//-------------------------------------------------------------------------------------------------------
//1. Add the starting square (or node) to the open list.
//2. Repeat the following:
// a) Look for the lowest F cost square on the open list. We refer to this as the current square.
// b) Switch it to the closed list.
// c) For each of the 8 squares adjacent to this current square …
// * If it is not walkable or if it is on the closed list, ignore it. Otherwise do the following.
// * If it isn't on the open list, add it to the open list. Make the current square the parent of this square.
// Record the F, G, and H costs of the square.
// * If it is on the open list already, check to see if this path to that square is better, using G cost as
// the measure. A lower G cost means that this is a better path. If so, change the parent of the square
// to the current square, and recalculate the G and F scores of the square. If you are keeping your open
// list sorted by F score, you may need to resort the list to account for the change.
//
// d) Stop when you:
// * Add the target square to the closed list, in which case the path has been found (see note below), or
// * Fail to find the target square, and the open list is empty. In this case, there is no path.
//3. Save the path. Working backwards from the target square, go from each square to its parent square until
// you reach the starting square. That is your path.
//-------------------------------------------------------------------------------------------------------
for some clarity
F is the shortest path, from node current
G is the goal
H is the cost to get from node current to node next,
heuristics are important to weight topographical changes in the pathfinding or dangers or impassable obsticles
Author
Step 3: If no best option was generated, expand "potentials" list to neighboring grid squares, repeat.
No, this would be a correct way to do it. The issue would be that in order to satisfy step 3, I would have to have a potentially huge list of potentials. Like, take a look at this:
http://i.imgur.com/vGWAE.jpg
(Square would be a member of the grid set, circle is a node, red lines are impassible obstacle lines)
The yellow lines would be my initial set. The green line is valid, but when it actually gets tested would be indetermined-- it might be 50 iterations in.
Meanwhile, any grid square that CAN'T reach that node has to go through *all* the possible iterations. This becomes a speed issue.
I think I'm going to go another direction and see if I can't make a floodfill/navmesh out of the area. Some of my navmesh polygons would be pretty small, especially in tight places, but I haven't read anywhere that that's a problem.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
