The closest node to the player
Author
I am working on a path-finding system for my game. Right now I made a map-editor tool that enables to manually add new nodes (waypoints) and to connect nodes together. After the map is loaded to the game's 3D scene the NPCs can move from every node to it's neighbours. Right now the NPCs choose a neighbour node randomly, but I want to add a pathfinding algorithm so that NPCs will be able to track the player (I am going to use A* ).
The problem:
Before tracking the player, the NPC must first know what node is the goal node. The goal node is the closest node to the player, but I don't know what is the closest node to the player unless I scan hundreds or maybe thousands of nodes coordinates which is not necessarily a good idea.
I thought about dividing the 3d scene into boxes or something, so I can scan nodes only in a small part of the entire 3d scene, but I just don't know exactly how to make it as simple and neat as possible.
I would be glad to know what you think.
[edited by - elijah on May 26, 2003 4:24:48 AM]
[edited by - elijah on May 26, 2003 4:25:56 AM]
I think a box-sort would be a good idea - divide the space into a 3d-grid and put the nodes inside each box in a linked list or something. Will you have to check for obstacles between player and nodes? That might complicate things a bit, and you might want to divide the space into ''rooms'' or something instead of a simple fixed grid.
Marijn
Marijn
Author
Obstacles between the player and the node is a part of my problem, but for now I''m willing to forgive the NPC if he searchs for a path to a node that has an obstacle.
I would really like to find some source code that demonstrates a solution to these kind of problems.
I would really like to find some source code that demonstrates a solution to these kind of problems.
Can''t you link the nodes into whatever system you''re using for culling the scene? If not, then you should look at partitioning them separately.
mwtb
Probably the easiest way is with an AABB tree.
M
--------------------------------------------------
"I have never let my schooling interfere with my education. " --- M.Twain
Marcus Hays
www.phrenicgames.com
M
--------------------------------------------------
"I have never let my schooling interfere with my education. " --- M.Twain
Marcus Hays
www.phrenicgames.com
Store your path nodes in a KD tree. The whole thing is a bit of a pain to figure out at first, but once you''re comfortable with the tree, you''ll love it.
No,no...
Make each node have a pointer to each neighbor, and to have a distance value stored for the distance to that neighbor. It is far simpler both to organize and to retreive the data (assuming the bot knows which node they are in). Besides that, just think how much memory you will consume by creating a complex structure like an AABB or KD tree for this. It''s using an elephant gun to swat a fly. (unless of course you are already using a partitioning algorithm for the map data, then go gung-ho)
Make each node have a pointer to each neighbor, and to have a distance value stored for the distance to that neighbor. It is far simpler both to organize and to retreive the data (assuming the bot knows which node they are in). Besides that, just think how much memory you will consume by creating a complex structure like an AABB or KD tree for this. It''s using an elephant gun to swat a fly. (unless of course you are already using a partitioning algorithm for the map data, then go gung-ho)
Just to add yet another suggestion, I would probably think about a quadtree.
Keep dividing untill there is only a single waypoint within each node, and then searching becomes trivial.
You know the start point is within the whole quadtree, which quadrant? Keep drilling down untill you reach a leaf node and you have the potentially closest waypoint.
I say potentially as the start point could be on the boundary of two quadrants, and although you are within this quadrant, the next could actually contain a closer waypoint. However, this might not be a problem as the distances involved should not be too great.
Alan
Keep dividing untill there is only a single waypoint within each node, and then searching becomes trivial.
You know the start point is within the whole quadtree, which quadrant? Keep drilling down untill you reach a leaf node and you have the potentially closest waypoint.
I say potentially as the start point could be on the boundary of two quadrants, and although you are within this quadrant, the next could actually contain a closer waypoint. However, this might not be a problem as the distances involved should not be too great.
Alan
Author
Really really thank you people for you're great responds, you opened my mind,
I think I know what I'm going to do. I'v already made an octree class for collision in my game and I'll make a variant of the octree class for the path-nodes.
Every box in the octree will be bound to a sphere.
I can also bind the player position to a sphere and scan for spheres intersection in the octree (I'll use a sphere to sphere intersection algorithm).
Then I'll check the closest node to the player only for the leafs that intersected.
[edited by - elijah on May 26, 2003 6:11:41 PM]
I think I know what I'm going to do. I'v already made an octree class for collision in my game and I'll make a variant of the octree class for the path-nodes.
Every box in the octree will be bound to a sphere.
I can also bind the player position to a sphere and scan for spheres intersection in the octree (I'll use a sphere to sphere intersection algorithm).
Then I'll check the closest node to the player only for the leafs that intersected.
[edited by - elijah on May 26, 2003 6:11:41 PM]
quote:Original post by MindCode
No,no...
Make each node have a pointer to each neighbor, and to have a distance value stored for the distance to that neighbor. It is far simpler both to organize and to retreive the data (assuming the bot knows which node they are in).
The problem with this is that path finding at this resolution is costly. Utilising an oct-tree (kd-tree or AABB tree) helps by partitioning the space into regions that are essentially identical in terms of the cost to move through them (i.e., no obstacles, no large changes in movement cost). Of course, there is always a tradeoff between representation and computation. An oct-tree might be quick and easy to perform pathfinding in, but it costs more to create. If you can create it offline then you''re ahead of the game. That''s not something you can do with A*. Of course, Dijkstra''s would suffice instead, but the storage cost of the results is prohibitive.
The moral is that every method has its pros and cons... it''s a matter of finding the optimal balance for the specific domain.
(Personally, for 3D environments I can certainly recommend staying away from A*... this is based on my experience of developing automated planning and replanning software for autonomous aircraft).
Cheers,
Timkin
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
