Hi, I have started to think about how I would go about implementing enemy AI into my game. I have read about A* (A star) path finding algorithm so that the enemies know how to reach the player.
Has anyone here got some experience in implementing the A* path finding algorithm on the NES? if not what algorithms are you guys using? my game is a top down type of experience btw. I'm thinking that this algorithm is a quite massive operation for the NES to handle, but I might be wrong.
So, I guess what I'm asking here is that you share your experience with these path finding algorithms.
A* path finding algorithm for enemy AI
Moderator: Moderators
Pac-Man monsters choose a target (either the player, several steps ahead of the player, on the other side of the player from another monster, or protecting the path to its favorite corner) and take one step at a time in the target's general direction.
The best answer will depend on your map geometry.
The best answer will depend on your map geometry.
Yes, I considered the method where the enemy moves directly in the players direction. If enemy x-pos is less than player x-pos then the enemy simply moves right to increase its x-pos, but then enemies will get stuck behind obstacles, even if they are programmed to turn when colliding with a obstacle. Consider this figure:
The enemy is in tile A, the target (player) is in tile B. Because B x-pos is greater than A x-pos the enemy will go right and basically get stuck. I think I need more intelligent enemies than this. That's why I asked about the path finding algorithms and if you have used them and what was the result, or are these algorithms (A*, Breadth-first search...) overkill for the NES?
The enemy is in tile A, the target (player) is in tile B. Because B x-pos is greater than A x-pos the enemy will go right and basically get stuck. I think I need more intelligent enemies than this. That's why I asked about the path finding algorithms and if you have used them and what was the result, or are these algorithms (A*, Breadth-first search...) overkill for the NES?
I don't know how much searching can be done in the roughly 30,000 cycles between one NMI and the next. That's why I keep recommending simpler things that might work, and that's why I keep asking questions to rule out those simpler things. You've given a level geometry case where Pac-Man's algorithms won't work (for which thank you), so let's continue:
Real-time or turn-based?
How many A's are there?
You can use Bresenham's algorithm to compute the line of sight path to a target. If this path is blocked, how does A learn where B is?
Real-time or turn-based?
How many A's are there?
You can use Bresenham's algorithm to compute the line of sight path to a target. If this path is blocked, how does A learn where B is?
I did something like this for my Minesweeper clone, I think it could be used for this, although might be very slow and maybe not possible on the NES.
What you'd do is read the square the person is on. Read every square around him (8 squares) save the ones that haven't been checked and can be moved on in an array. Repeat until one of them ends up on square you want. That will be the shortest path. Although I can't think of a good way to implement this ATM.
What you'd do is read the square the person is on. Read every square around him (8 squares) save the ones that haven't been checked and can be moved on in an array. Repeat until one of them ends up on square you want. That will be the shortest path. Although I can't think of a good way to implement this ATM.
I have experience implementing games on other platforms (mostly rogue likes) and in my experience A* pathfinding is rarely needed for a game. Think about how often you will actually need pathing to overcome your level design, then think about how it will impact the game if the enemy gets stuck. Most of the time getting stuck is not going to break your game or give your player a bad experience.
If you actually do need A* pathing you can break it up over several frames. Because the algorithm is stack-based as long as you do not overwrite the stack between frames you can pick up where you left off and process another N path tiles. Besides, your enemies will not need to update their destination every frame. Every 10 or 20 should be enough even for a fast game.
If you actually do need A* pathing you can break it up over several frames. Because the algorithm is stack-based as long as you do not overwrite the stack between frames you can pick up where you left off and process another N path tiles. Besides, your enemies will not need to update their destination every frame. Every 10 or 20 should be enough even for a fast game.
Yeah, I'm all for simple things as well.tepples wrote:That's why I keep recommending simpler things that might work
Ok, good.tepples wrote:and that's why I keep asking questions to rule out those simpler things.
I'm sorry I didn't explain the circumstances thoroughly before, even asking the right questions can be difficult sometimes.tepples wrote:You've given a level geometry case where Pac-Man's algorithms won't work (for which thank you)
The game I'm working on is a real-time type of game, in fact I have recently uploaded a short youtube video here about the game.tepples wrote:Real-time or turn-based?
As of now there are no enemies (A's), and unfortunately I don't know how many there will be at this time. That is also part of why I want to know these things, like what can be done with the NES, and I'm not looking for the most impressive piece of code but maybe the simplest method of doing as intelligent enemies as it takes for the game to be at least decent or good. If you really want a number I would have to say one to five or six at the most.tepples wrote:How many A's are there?
This actually looks promising, I didn't know about this algorithm as all of these things are quite new to me.tepples wrote:You can use Bresenham's algorithm to compute the line of sight path to a target.
Ok, maybe A can run around a little randomly until the line of sight isn't blocked, and then go for the target (B). This is definitely an option worth considering I think.tepples wrote:If this path is blocked, how does A learn where B is?
-
UncleSporky
- Posts: 388
- Joined: Sat Nov 17, 2007 8:44 pm
Truly random movement is kind of annoying and dumb looking, in my opinion. The standard method of "pick random direction, walk, pick another random direction" usually results in a lot of fiddly walking in circles.
One good method to circumvent this that I once used is to store the current walking direction for each enemy, and randomly modify it to the left or right. 0-32 = up, 33-64 = right, 65-96 = down, 97-128 = left, or break it into diagonals if you're using them. Add some amount like 8 if they randomly turn right, subtract if they turn left. This results in wide snaking paths (more apparent with diagonal movement).
Another method that I that I think I like better is like the target-based Pac-Man method. It works better as a general method for all pathfinding. In a nutshell:
All monsters have a target x/y value on the map that they are trying to reach at all times. This can be the player, updated whenever the player moves, or maintained as the "last seen" position of the player before he moved out of sight. The target can also be a random location when you want them to move randomly, they'll seem to move purposefully toward a certain room or location.
Monsters have a flag indicating horizontal or vertical movement that alternates every turn. Movement in a direction can fail if it would result in hitting a wall or the x/y value is already correct (equal to their target's x/y value). If x movement is attempted toward the target and fails, the flag is not updated and y movement is attempted instead. If both movements fail, it will randomly choose a new target some distance away from its current location.
This way monsters will follow walls and corridors to get to their target if need be, and eventually give up and start walking randomly.
One good method to circumvent this that I once used is to store the current walking direction for each enemy, and randomly modify it to the left or right. 0-32 = up, 33-64 = right, 65-96 = down, 97-128 = left, or break it into diagonals if you're using them. Add some amount like 8 if they randomly turn right, subtract if they turn left. This results in wide snaking paths (more apparent with diagonal movement).
Another method that I that I think I like better is like the target-based Pac-Man method. It works better as a general method for all pathfinding. In a nutshell:
All monsters have a target x/y value on the map that they are trying to reach at all times. This can be the player, updated whenever the player moves, or maintained as the "last seen" position of the player before he moved out of sight. The target can also be a random location when you want them to move randomly, they'll seem to move purposefully toward a certain room or location.
Monsters have a flag indicating horizontal or vertical movement that alternates every turn. Movement in a direction can fail if it would result in hitting a wall or the x/y value is already correct (equal to their target's x/y value). If x movement is attempted toward the target and fails, the flag is not updated and y movement is attempted instead. If both movements fail, it will randomly choose a new target some distance away from its current location.
This way monsters will follow walls and corridors to get to their target if need be, and eventually give up and start walking randomly.
I only made algorithems that a list of paths are made and it takes which one is the shortest path to get to the target, the enemy. it also compensated for if the player is going up at the time or down. Note that this might suck as an idea for the cpu time required for making a path and calculating the shortest distance. but you could hard map some paths. but still.
I made the enemy save the players momentary position as his target, then try to line up either X or Y first (first direction is chosen randomly) and then line up the other direction until he reaches his target. By the time he reaches his target position, the player may be long gone, so then he takes the player's new momentary coordinates as his new target.
This far I have done and it's working quite ok, here is a ROM so you can see for yourself.
Then I was thinking that when the enemy hits a wall, he will move kind of randomly for a while, maybe some few seconds or so, after which he will save a new target and try again. This might work with the level design I use, I still need to try this.
This far I have done and it's working quite ok, here is a ROM so you can see for yourself.
Then I was thinking that when the enemy hits a wall, he will move kind of randomly for a while, maybe some few seconds or so, after which he will save a new target and try again. This might work with the level design I use, I still need to try this.