pathfinding and chasing
Author
Hi. I was reading about pathfinding to try to implement it to my pacman game, but i still have lot of doubts.
First, all the articles of the A* algorithm says the was pathfinding is with it, but never mentioned how to get the minimun number of squares(tiles, or whatever it is)between one object and another. I tried to find a formula but i was unsuccesful.
My other doubt is about the enemy chasing pacman. I think pathfinding will work in some cases but i need something a little bit different, for example...... I need the enemy just moving and detecting the new ways to go around i mean, if the enemy encounters a cross where there are 3 paths to choose, choose one like in random, and then if the pacman is seen, then start chasing him, until it loses it.
What do you think, what algorithm do you recomend me?, What can i do to do this?
Quote:Original post by Dospro
First, all the articles of the A* algorithm says the was pathfinding is with it, but never mentioned how to get the minimun number of squares(tiles, or whatever it is)between one object and another. I tried to find a formula but i was unsuccesful.
The minimum might be manhattan distance (difference in X plus difference in Y), or pythagorean distance (the square root of the difference in X plus the difference in Y squared), depending on whether you can make diagonal moves or not. In most Pacman games you can't, so the former makes sense. You can count it and verify it for yourself.
Quote:for example...... I need the enemy just moving and detecting the new ways to go around i mean, if the enemy encounters a cross where there are 3 paths to choose, choose one like in random, and then if the pacman is seen, then start chasing him, until it loses it.
What do you think, what algorithm do you recomend me?, What can i do to do this?
Well, the algorithm is right there, in what you said:
if at junction: if can see pacman: follow pacman else: pick random directionJust think about it in broad terms, make some notes, and most of the answers will come to you. Obviously you then have to decide exactly what 'follow pacman' and 'pick random direction' mean, but such is the nature of problem-solving - start with the outline and drill down.
Author
I dont care having to enlarge my credits list....
But thanks for the help, i will try to implement it myself and also see whats the code about.....
Thanks for your help.
But thanks for the help, i will try to implement it myself and also see whats the code about.....
Thanks for your help.
Actually, there's a very easy way to go about chasing, probably even less intense than using A* or checking visibility.
Do what ants do with Pac-man. So, you have two different entities, ghosts and pac-man. As pac-man moves along, he leaves a pheromone trail that gradually evaporates. The ghosts do the same, but they have a tendency to follow the path with the stronger pheromone as they come to cross roads. This will cause the ghosts to chase after pac-man when they pick up his scent. If done right, this will also create clustering among the ghosts as the chase after pac-man.
Of course, pheromone trails aren't deterministic. Its a probabilitic process. So, at a crossroad, a ghost may still chose a different path probabilistically. Its just that they will have the tendency to move in the direction (to the next square or tile) with a strong pheromone scent than the others around it. The slight randomness will inject some randomness into the ghosts' movement, not to mention possibly create a swarming like behavior.
This is completely based on Ant Colony Optimization and Ant System research. You should be able to find the stuff on google, along with the probabilistic function used to determine the next space to move to.
Do what ants do with Pac-man. So, you have two different entities, ghosts and pac-man. As pac-man moves along, he leaves a pheromone trail that gradually evaporates. The ghosts do the same, but they have a tendency to follow the path with the stronger pheromone as they come to cross roads. This will cause the ghosts to chase after pac-man when they pick up his scent. If done right, this will also create clustering among the ghosts as the chase after pac-man.
Of course, pheromone trails aren't deterministic. Its a probabilitic process. So, at a crossroad, a ghost may still chose a different path probabilistically. Its just that they will have the tendency to move in the direction (to the next square or tile) with a strong pheromone scent than the others around it. The slight randomness will inject some randomness into the ghosts' movement, not to mention possibly create a swarming like behavior.
This is completely based on Ant Colony Optimization and Ant System research. You should be able to find the stuff on google, along with the probabilistic function used to determine the next space to move to.
When you expand a node in a*, give each node a counter, witch = the counter of the node it expanded from + 1. When you hit the pathfinding goal, that node's counter should be the number of steps your shortest path would need.
With this you could add a treshold, so that if the number of steps to reach pack-man is > X, you lost him.
This wil not take corners int acount, so seeing packman should use another algo.
Since there are no open spaces in pack-man, a simple _is_he_on_my_horisontal_row_before_any_walls_ and
_is_he_on_my_vertical_colum_before_any_walls_ test should do it!
this way you have two states:
CHASE:
find shortest path.
if path it to long, your LOST.
LOST:
move in one direction, and see if you could move in another.
if you SEE pack_man, CHASE him.
DEAD:
find shortest path to CENTER, and go that way.
-Anders
With this you could add a treshold, so that if the number of steps to reach pack-man is > X, you lost him.
This wil not take corners int acount, so seeing packman should use another algo.
Since there are no open spaces in pack-man, a simple _is_he_on_my_horisontal_row_before_any_walls_ and
_is_he_on_my_vertical_colum_before_any_walls_ test should do it!
this way you have two states:
CHASE:
find shortest path.
if path it to long, your LOST.
LOST:
move in one direction, and see if you could move in another.
if you SEE pack_man, CHASE him.
DEAD:
find shortest path to CENTER, and go that way.
-Anders
Author
Really make me think.
No i have this problem.
Remember that pacman is always moving, and the a* works perfect with static units.
So just guessing, i think that the a* will try to find the best path but with each movement, this will make the enemy move to one side and the opposite if you the same, its not bad, but its no what i want.
I want that for example:
-------------------------------------------
N
---------
P
-------------------------------------------
N is enemy and P pacman.
So with a* the algorithm would go left, then down and finally right.
Well, if in that movements the pacman decide to change some tiles to the right, then the enemy should just cancel the left moving and now start moving right which is now the best path.
I want to take an actio and do not cancel it until its really necesary, i mean: if pacman moves to right, continue te the left path and instead of going to the previos pacman tile, then go to the new one.
Its kinda wreid. but i need IA not REALLY intelligent, i will try to implement some algorithms to see what happens...
THanks for the help
No i have this problem.
Remember that pacman is always moving, and the a* works perfect with static units.
So just guessing, i think that the a* will try to find the best path but with each movement, this will make the enemy move to one side and the opposite if you the same, its not bad, but its no what i want.
I want that for example:
-------------------------------------------
N
---------
P
-------------------------------------------
N is enemy and P pacman.
So with a* the algorithm would go left, then down and finally right.
Well, if in that movements the pacman decide to change some tiles to the right, then the enemy should just cancel the left moving and now start moving right which is now the best path.
I want to take an actio and do not cancel it until its really necesary, i mean: if pacman moves to right, continue te the left path and instead of going to the previos pacman tile, then go to the new one.
Its kinda wreid. but i need IA not REALLY intelligent, i will try to implement some algorithms to see what happens...
THanks for the help
Answer to your last problem!
Think of the movement as static tile-steps,
and then think about the smooth movement as interpolation of positions for
nicer graphics / eye-candy (big AAA titles do this :-) )
So:
When pac-man or goast are moving from TileA, to TileB, give them the _tile_ position at TileB, because they cant change direction until they reach B, and its nice that the AI plans a little ahead! :-) This way, the gosts wil chase the tile pac-man are going into, and not pac-mans real position! (I hope you have tiles in your game, or else, getting A* nodes would be a problem.)
How you implement this is not so important, as long as you have some _tile_ positions for all units. your AI dont realy need to know that they have smooth movement from A to B (some care should be taken in the gost-vision system :-) ),
and taking this information away from your AI should only make it simpler and better. You also only need to recalc pathfinding and stuff when a unit reaches its _tile_ position, since this is the only time it can change direction! Not so big speedup for pac-man, but think about 1000 units in an epic rts!
-Anders
Think of the movement as static tile-steps,
and then think about the smooth movement as interpolation of positions for
nicer graphics / eye-candy (big AAA titles do this :-) )
So:
When pac-man or goast are moving from TileA, to TileB, give them the _tile_ position at TileB, because they cant change direction until they reach B, and its nice that the AI plans a little ahead! :-) This way, the gosts wil chase the tile pac-man are going into, and not pac-mans real position! (I hope you have tiles in your game, or else, getting A* nodes would be a problem.)
How you implement this is not so important, as long as you have some _tile_ positions for all units. your AI dont realy need to know that they have smooth movement from A to B (some care should be taken in the gost-vision system :-) ),
and taking this information away from your AI should only make it simpler and better. You also only need to recalc pathfinding and stuff when a unit reaches its _tile_ position, since this is the only time it can change direction! Not so big speedup for pac-man, but think about 1000 units in an epic rts!
-Anders
Rule #1 in developing anything: "When you have a hammer, everything looks like a nail."
So, the first question here is, do we really need A*? If you're using this pac-man game as a demonstration of how A* works, then I guess the rest of my arguments are pointless and you can skip this post.
If, this is not an application specific for demonstrating A*, then we can pose the question of do you really need it? Yes, its nice and all when it comes to finding shortest paths in tile based games, but then it implies a global view? Do ghosts have an omnipotent global view? Do you want them to have a global view? Personally, I don't think ghosts should have global views because then it will make escaping from them that much tougher, consider that they move just that slightly faster than pac-man anyways. So, then what may happen if you use A* is that the game turns into how long can you survive with every ghost chasing you constantly?
Traditionally, I probably don't have anything to back this up, but I feel ghosts in pac-man just randomly move around until they actually "see" pac-man. Then they simply follow pac-man. So, if you do A* during the "chase" process, then that might make sense, but will still make escaping near impossible, since ghosts will literally come at you from all sides.
Since ghosts move slightly faster than pac-man anyways, I think that for game balance purposes, something as complex as A* may not be needed to get the effect you want. Just random movement, short range visibility checks, and simple chasing should suffice. Of course, this is all personal opinion. So, its not that I'm criticizing you for using A*, just that I'm presenting a different prespective.
So, the first question here is, do we really need A*? If you're using this pac-man game as a demonstration of how A* works, then I guess the rest of my arguments are pointless and you can skip this post.
If, this is not an application specific for demonstrating A*, then we can pose the question of do you really need it? Yes, its nice and all when it comes to finding shortest paths in tile based games, but then it implies a global view? Do ghosts have an omnipotent global view? Do you want them to have a global view? Personally, I don't think ghosts should have global views because then it will make escaping from them that much tougher, consider that they move just that slightly faster than pac-man anyways. So, then what may happen if you use A* is that the game turns into how long can you survive with every ghost chasing you constantly?
Traditionally, I probably don't have anything to back this up, but I feel ghosts in pac-man just randomly move around until they actually "see" pac-man. Then they simply follow pac-man. So, if you do A* during the "chase" process, then that might make sense, but will still make escaping near impossible, since ghosts will literally come at you from all sides.
Since ghosts move slightly faster than pac-man anyways, I think that for game balance purposes, something as complex as A* may not be needed to get the effect you want. Just random movement, short range visibility checks, and simple chasing should suffice. Of course, this is all personal opinion. So, its not that I'm criticizing you for using A*, just that I'm presenting a different prespective.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
