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?
Pathfinding with nodes... finding the first node.
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.
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.
"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.
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.
Author
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!
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!
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.
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.
Author
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.
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.
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.
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.
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?
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?
Author
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
