Jump to content

  • Log In with Google      Sign In   
  • Create Account


Pathfinding with nodes... finding the first node.


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
24 replies to this topic

#1 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 23 November 2012 - 04:41 PM

Hi all,

I've implemented an a* node pathfinder. Everything works great, except one thing: finding a node to start at.

In order for a node to be acceptable, there's a "clear path" test that I run-- as in, can I draw a straight line to this node and not encounter any obstacles.

My problem is, the "clear path" test, while not cpu-intensive, is *too* CPU intensive to run through every single node. I'm trying to figure out a good way to narrow down the nodes I am going to test.

My first thought was to maintain a grid and a set of pointers to possible nodes, but I have a problem in that a node might be accessible from one section of a grid square, but not another-- or worse, a node might actually be accessible from the grid square, but not from any of the arbitrary points I choose to test.

I've considered a polygon mesh with pointers to nodes, but since my node system has to autogenerate (user created levels) from a field of lines and circles, I haven't been able to come up with any sensible algorthm to generate a polygon mesh that works every time.

A friend suggested to me that I give each node a radius and preprocess them to see which one can be accessed from arbitrary points on the screen-- and then if the player is within the radius of the node, it can do the clear site. This is a good solution, but because the game has a lot of open areas, the nodes tend to inflate to the point where only a few get culled out, and it's almost no help at all.

Does anyone have a creative solution for narrowing down the node tests?

Sponsor:

#2 Kyall   Members   -  Reputation: 287

Like
0Likes
Like

Posted 23 November 2012 - 10:06 PM

I don't quite understand what you're trying to achieve. Can you provide some example mechanics that require this code. Say a description of the game you hope to build or what you want to achieve.

I'm going to use the example of an RTS just to take a wild stab at what you need and then go on from there.

Player creates a map, this map can be described as a series of nodes / areas that have barriers between different nodes. A collection of nodes that are separated from different collection of nodes is a cordoned off area. To find the different areas, and hence to determine what nodes can be linked to each other, we need to generate an area id for each of these cordoned off areas.

MAP:
0 0 0 0 0 X 0
0 X 0 X 0 X 0
0 0 0 0 X 0 0
0 0 0 0 X 0 0
0 0 0 0 0 X 0

So we have a map, that describes each node and their links just to their neighboring nodes, and we add all of these nodes to a list to be processed.
We pick the first node in this process list, and we pick an area id of #1. We then assign #1 as the area id for this node, all of it's accessible neighbors, and all of it's accessible neighbors' neighbors and so forth until there are no more neighbors that can be assigned the area id of 1. As we do this we remove each node that has an area id assigned to it from the processing list.

MAP: Area ID 1 assigned
1 1 1 1 1 X 0
1 X 1 X 1 X 0
1 1 1 1 X 0 0
1 1 1 1 X 0 0
1 1 1 1 1 X 0

We then go back and pick the first remaining node in the process list, and repeat the same process with area id #2. And so forth until the processing list is empty.

MAP: Area ID 2 assigned
1 1 1 1 1 X 2
1 X 1 X 1 X 2
1 1 1 1 X 2 2
1 1 1 1 X 2 2
1 1 1 1 1 X 2

We now have a map of every cordoned off area by an area id.

If we were going to place player's starting positions and resource locations for an RTS in this map accordingly, we find the biggest area ( the area with the most number of nodes ) and we place these items there.

For game quality we can also generate connectivity heat maps as well as distance heat maps. A connectivity heat map would show bottle-necked zones in an area, say a zone of 10 nodes that is only accessible from 1 node, and we can use these bottlenecks as places to stash resources so these zones can be strategically controlled with few buildings/units thanks to the player putting it's defenses at a bottleneck. We can also use this map to place the player's starting bases in vulnerable positions, say areas that consist of 10 nodes connected to by at least 10 other nodes. And we generate a distance map, that is made up of 3 components; a distance from a center of mass node, a distance from the top and a distance from the left. We can combine this map with the connectivity map to place the players in ideal positions that are strategically vulnerable but far apart.

I hope these examples help some what.

Edited by Kyall, 23 November 2012 - 10:08 PM.

I say Code! You say Build! Code! Build! Code! Build! Can I get a woop-woop? Woop! Woop!

#3 C0lumbo   Crossbones+   -  Reputation: 2197

Like
0Likes
Like

Posted 24 November 2012 - 02:16 AM

"A friend suggested to me that I give each node a radius and preprocess them to see which one can be accessed from arbitrary points on the screen-- and then if the player is within the radius of the node, it can do the clear site. This is a good solution, but because the game has a lot of open areas, the nodes tend to inflate to the point where only a few get culled out, and it's almost no help at all."

If you did this to get a list of viable nodes, then chose one of them based on some heuristic that might include closest-to-units-position and in-roughly-the-direction-it's-heading, then would that work.

In general though, I tend to have my AI maintain knowledge of what waypoint they're at. They're spawned at a waypoint, and when they move, they follow waypoints, so it's easy to always know which waypoint they're at. It's easy to conceive of situations where this might not be possible (e.g. if AI took over a player character temporarily). A bit more info about the problem might help.

#4 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 24 November 2012 - 12:17 PM

Okay, let me try to clarify...

I'm under NDA, so I can't post a game screenshot. This is a mockup. White places are blocking, can't walk through them. Blue circles are pathing nodes auto-generated around the white spaces by internal algorithm-- the idea is that no matter where you are, you have a fairly straight path to a pertinent node, and pointless nodes get culled.

Simplified Mockup:
http://i.imgur.com/xFxXm.jpg

Note that in real game, play area is many screens wide, and a worst case scenario might be 10-20k nodes, if a user creates a complex level.

Now: For speed reasons (targetting iPhone), the enemy AI typically walks straight at the player. Much of the game is open space, so this works fine in many cases. An enemy checks every now any again to see if it's not possible to walk to the player-- just does a line of sight test, any intersection with a blocking line or circle or polygon, and test fails. Enemy now goes into pathfinder mode.

Pathfinder mode needs to detect possible nodes from the player's position to start pathfinding. For instance, a node on the other side of the white line isn't pertinent. In fact, only a node that can have a straight line drawn to the player is pertinent.

Currently, the game just works by testing all nodes-- simply "draw line from node 1 to player, yes no? Draw line from node 2 to player, yes no?" With only a few nodes, works fine, but as the numbers get up there, doing the line test gets nasty.

So we've tried a few gridding and area tests, all of which seem to be impractical either in terms of speed, memory, or ability to be autogenerated within certain game parameters (mostly gen speed).

I'm looking for a novel idea. There must be some out there-- doesn't every node based AI have to do a "which nodes are pertinent to walk to first?"

Thanks!

#5 C0lumbo   Crossbones+   -  Reputation: 2197

Like
0Likes
Like

Posted 24 November 2012 - 12:35 PM

So if I understand the problem, when your AI go into pathfinder mode, you actually don't know the start node or the end node of your desired path.

Perhaps you can work out the start node (one that the AI can reach in a direct path) by caching some information in your walls so that when the AI walks into the wall, it can be told a node that he can definitely get to.

Then start your A* path without knowledge of what your destination point. For each node you visit, you do your straight line test to the player, and as soon as one succeeds, your pathfinding can finish.

#6 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 25 November 2012 - 10:10 AM

Yeah... when they go into pathing mode, they're just "somewhere." And they need to know each node they can actually reach, to include it in the pathing test.

Some creatures are more intelligent than others-- they pathfind without having to hit a wall first (think of it as a mob of mindless things, and then a few brain things scattered in the mix).

I suppose polygons are my only real option, but damned if I can figure out a data structure that both can be autogenerated, and would be quick.

#7 Steve_Segreto   Crossbones+   -  Reputation: 1510

Like
0Likes
Like

Posted 26 November 2012 - 02:03 AM

I'm looking for a novel idea. There must be some out there-- doesn't every node based AI have to do a "which nodes are pertinent to walk to first?"


What you described is called a "heuristic". One of the common ones for A* is to sort potential path nodes by Manhattan distance and explore them in that order. Not sure if this helps you with your problem, I still don't quite understand what trouble you are facing.

#8 Kyall   Members   -  Reputation: 287

Like
0Likes
Like

Posted 26 November 2012 - 02:45 AM

So when you said you were looking for which node to start at you meant which node should get the highest priority for searching based on the direction to the player. And then from that point on which node to choose to move to first. I'm going to guess use a dot product of the direction from the starting point to the player and the difference vector between the test node and the previous node to make a straight line focussed heuristic to search with.
I say Code! You say Build! Code! Build! Code! Build! Can I get a woop-woop? Woop! Woop!

#9 Olof Hedman   Crossbones+   -  Reputation: 2739

Like
0Likes
Like

Posted 26 November 2012 - 03:14 AM

How about always keeping track of which node you are closest to? (even when not in "path finder mode")
You only need to check if any of the neighbours of the node is closer to you then the node, then you can switch, shouldn't be that cpu intensive?

Edited by Olof Hedman, 26 November 2012 - 03:16 AM.


#10 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 29 November 2012 - 08:44 AM

Olof: The problem with that is that not all accessible nodes will necessarily be close. One could be half the playfield away, but has a straight line to it.

We have considered putting in extra nodes, so that we COULD quarantine regions and make proximity or gridding a factor-- but the problem becomes tight spaces-- it would be possible to create a line configuration that chops an area in half, and then have a situation come up where no nearby nodes are actually accessible-- you'd have to walk to other, non-nearby nodes first.

#11 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

Posted 29 November 2012 - 08:55 AM

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.

Edited by BCullis, 29 November 2012 - 08:55 AM.

Hazard Pay :: FPS/RTS in SharpDX
DeviantArt :: Because right-brain needs love too

#12 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 29 November 2012 - 02:22 PM

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.

Edited by JohnnyLightwave, 29 November 2012 - 02:23 PM.


#13 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

Posted 29 November 2012 - 02:32 PM

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)?
Hazard Pay :: FPS/RTS in SharpDX
DeviantArt :: Because right-brain needs love too

#14 Steve_Segreto   Crossbones+   -  Reputation: 1510

Like
0Likes
Like

Posted 29 November 2012 - 05:57 PM

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?

#15 amrazek111   Members   -  Reputation: 692

Like
0Likes
Like

Posted 30 November 2012 - 08:18 PM

This seems like a great case for a navigation mesh. Is there a particular reason you want to use a node-based solution instead?

#16 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 04 December 2012 - 05:23 AM

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.

#17 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 04 December 2012 - 05:27 AM


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)?


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?

Edited by JohnnyLightwave, 04 December 2012 - 05:41 AM.


#18 BCullis   Crossbones+   -  Reputation: 1813

Like
0Likes
Like

Posted 04 December 2012 - 08:49 AM

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?
Hazard Pay :: FPS/RTS in SharpDX
DeviantArt :: Because right-brain needs love too

#19 Jedilamma   Members   -  Reputation: 103

Like
0Likes
Like

Posted 04 December 2012 - 10:02 AM

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

Edited by Jedilamma, 04 December 2012 - 10:05 AM.


#20 JohnnyLightwave   Members   -  Reputation: 142

Like
0Likes
Like

Posted 05 December 2012 - 08:02 AM

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.

Edited by JohnnyLightwave, 05 December 2012 - 08:05 AM.





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS