Edited by - Yanroy on 5/4/00 7:35:07 AM
Weird Pathfinding AI
Author
For my MUD, I need a way to make the NPCs follow people and seek them. I would use the A* algorithm, but I have a somewhat unique problem (I think...) Instead of having places on the map where you can't walk (i.e. rocks, water, anything else impassible), I don't have anything there. Look at this example (x indicates where there is a map square, ' ' is just dead space NOT empty array elements because there isn't any array):
x
x
x
xxxxxxxxxxxxxxxxxxxxxxxx
x x
x x
x x
I hope you can see the problem here. If I have an NPC in the lower left corner, and there is an enemy (human) on that spoke sticking out of the top, how do I make the NPC find the path to the human? There is no array to use the A* algorithm on. I can't determine whether it is even north or south without trying all possible paths! I know this can be fixed... other MUDs have done it.
Just noticed a couple of errors in the post
Edited by - Yanroy on 5/4/00 7:35:07 AM
Edited by - Yanroy on 5/4/00 7:35:07 AM
Actually the A* algorithm is defined to work with nodes, not array elements. In your case the x:es in your drawing is your node. Each node must have knowledge of the nodes they are connected to. Then as the A* algorithm visits a node it adds the nodes neighbours to the next possible nodes.
The A* star algorithm doesn''t need to know which direction is north, all it cares about is the cost for walking to where it is and the cost it has left to the goal. Of course it doesn''t know the cost left so it has to guess. You need to have some way of guessing the distance between two nodes, I would suggest comparing their coordinates. If the nodes have absolutely no idea where they are relative each other the A* must guess that the cost left is zero. That way it will search in an expanding circle around the start until it reaches the goal.
I hope I made any sense amidst my ramblings.
- WitchLord
The A* star algorithm doesn''t need to know which direction is north, all it cares about is the cost for walking to where it is and the cost it has left to the goal. Of course it doesn''t know the cost left so it has to guess. You need to have some way of guessing the distance between two nodes, I would suggest comparing their coordinates. If the nodes have absolutely no idea where they are relative each other the A* must guess that the cost left is zero. That way it will search in an expanding circle around the start until it reaches the goal.
I hope I made any sense amidst my ramblings.
- WitchLord
Author
I suppose I should have said this before.... In order to get the cost of going to a specific place, I need to run the A* algorithm, which needs a cost.... I didn''t know you could use a constant cost. The other thing is, there aren''t any coordinates whatsoever. In fact, different groups of nodes don''t even know other groups exist. It is extreemly compartmentalized (that is usually good, right? 
) The reason for that is I have a MUD namespace, containing, among other things, a list of Areas, which in turn contain lists of Locations, which contain lists of players and items. All the Locations in one Area are connected to each other, but the Area itself forms the bridge from the inside Locations to the Locations of an adjacent Area. (btw, the Area''s are only adjacent in the sense they are connected to each other). I will see if I can work A* into this...
--------------------
You are not a real programmer until you end all your sentences with semicolons;
) The reason for that is I have a MUD namespace, containing, among other things, a list of Areas, which in turn contain lists of Locations, which contain lists of players and items. All the Locations in one Area are connected to each other, but the Area itself forms the bridge from the inside Locations to the Locations of an adjacent Area. (btw, the Area''s are only adjacent in the sense they are connected to each other). I will see if I can work A* into this... --------------------
You are not a real programmer until you end all your sentences with semicolons;
Visit the ROAD Programming Website for more programming help.
Ah, you mean to say that you don''t know how to formulate a good heuristic since the space is not necessarily 2D An A* search without the heuristic is essentially just a ''breadth-first'' search, I believe, as you have no way of knowing which is the best node except for how far you have already travelled.
Let''s look at this slightly differently. Try calculating in advance which Areas are linked to other areas. Then your first job is to plot the list of areas from the start area to the finish area: this should be really quick, even with something like breadth-first search.
Once you have that list, you just need to
(a) plot the path from the start room to the room with the exit to the 2nd area on the list
(b) plot paths through each area to the exit to the following area
(c) plot a path from the entry to the last area to the target.
This way, you have essentially reduced the number of nodes you need to search to just the relevant areas. If you manage to search an entire area without finding a path from one external link to the other, you probably have a weird area setup, which could be a problem
Personally I wouldn''t try and work the A* heuristic into this, as it''s not really suited to this task, since your rooms and areas are not necessarily linked in any logical way. Most MUDs with the tracking skill just use a simple depth-first search without the area-based optimisation I detailed above.
An A* search without the heuristic is essentially just a ''breadth-first'' search, I believe, as you have no way of knowing which is the best node except for how far you have already travelled.Let''s look at this slightly differently. Try calculating in advance which Areas are linked to other areas. Then your first job is to plot the list of areas from the start area to the finish area: this should be really quick, even with something like breadth-first search.
Once you have that list, you just need to
(a) plot the path from the start room to the room with the exit to the 2nd area on the list
(b) plot paths through each area to the exit to the following area
(c) plot a path from the entry to the last area to the target.
This way, you have essentially reduced the number of nodes you need to search to just the relevant areas. If you manage to search an entire area without finding a path from one external link to the other, you probably have a weird area setup, which could be a problem
Personally I wouldn''t try and work the A* heuristic into this, as it''s not really suited to this task, since your rooms and areas are not necessarily linked in any logical way. Most MUDs with the tracking skill just use a simple depth-first search without the area-based optimisation I detailed above.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
