Simple, Cheap Pathfinding (from AI Game Programming Wisdom)
Author
I have a question about the article in AI Game Programming Wisdom; Simple, Cheap Pathfinding (pg. 155).
In this article the author uses sensors/whiskers to detect whether moveable areas are near the bot and how close it is to non-moveable areas (including other bots). It does this by simply going through the pixels within and area and direction and detects whether or not it is the background color.
Anyway.. the problem I'm having is how to efficiently apply this to a real game. A simple game, no doubt, but a game nonetheless. In my particular game (as with any, I'd imagine), the background is not one single color. It is a bunch of 32x32 images are multitudes of colors, especially when overlaying another. A grassy 32x32 tile, for example, has more than 1 color in it (obviously).
I'm sure you're thinking "well, just mark each tile with a moveabe flag, simple." Right, but that's not the problem. That's a given when doing collision detection on map items. However, I'm not sure how to handle other bots in the game. If I loop through each individual bot to see if its within the radius of the sensors/whiskers, I'd have a highly inefficient collision detection system. 20 bots on the screen, each attempting to determine if each other is within the others sensor/whisker range, would be a 20x20 (400 total) loop. My math may be off (it might be less), but I think I make my point.
It comes down to this: How do I efficiently sense other moveable objects without having to go through tons of looping each frame?
Thanks in advance.
Quote:Original post by wyrd
It comes down to this: How do I efficiently sense other moveable objects without having to go through tons of looping each frame?
Thanks in advance.
It seems to me that you can obtain some savings by encompassing your map in various bounding volumes and testing for collisions between these areas. If there is no collision, then all of the objects within will not have a collision. If there *IS* a collision, then you'll need to check each individual within the bounding volume to determine actual collisions. (Additionally, you could partition each bounding volume into a set of smaller bounding volumes as much as needed).
Even though you have some additional overhead with setting up and handling these bounding volumes, you can obtain significant savings by eliminating groups of objects with only one check.
There are other issues that I'm ignoring (such as an object crossing a bounding volume boundary, how to pick efficient bounding volumes, etc.) Unless I'm misunderstanding your problem, this should give you an approach to try out.
First, I highly suggest to drop any path finding algorithms besides for A*, and implement A* in your engine, it's by far the best path finding algorithm up to date (in terms of speed/accuracy). It's also relatively simple to implement.
As for your original problem, divide the map in 'movement tiles'. A movement tile is a predefined area which has various info about the corresponding relief (plain, mountain, hill, sea, walls, forest, etc.)
Give any relief type a value, lower being better. That is, plain has 0, forest has 1, and areas that can not be travelled should be 127.
Each unit should modify the last bit from that movement tile it sits on, so that if it is over an area that area's last bit will be set as 1. When it leaves that area, it should set the bit to 0.
For small units that use only one movement tile, that's very easy to implement. For bigger units it's a little more harder, but doable.
As for your original problem, divide the map in 'movement tiles'. A movement tile is a predefined area which has various info about the corresponding relief (plain, mountain, hill, sea, walls, forest, etc.)
Give any relief type a value, lower being better. That is, plain has 0, forest has 1, and areas that can not be travelled should be 127.
Each unit should modify the last bit from that movement tile it sits on, so that if it is over an area that area's last bit will be set as 1. When it leaves that area, it should set the bit to 0.
For small units that use only one movement tile, that's very easy to implement. For bigger units it's a little more harder, but doable.
Author
AP:
That's exactly what I was thinking. Except I was just going to keep one boundry, and that would be around the players character. Anything that is not within the players boundry will simply be ignored and not do any AI. With the relative simplicity of my game this should work fine (there's no reason for monsters to roam around which aren't visible to the player). Is this the best approach, or are there other alternatives?
Raduprv:
I plan on making this for PDA devices. Obviously I'm new to this (hence the reason why this topic is in the For Beginners forum), and I'd like to keep things fairly simple for my first time (well, okay maybe not first game, but first PDA game). I don't want to add any needless processing unless I have to. I would like to have quite a few enemies on the screen without taxing the PDA more than I have to. If this simplistic movement scheme is too simple and the bots don't seem smart enough, then I will have to look into A* pathfinding. But until then, I'd like to try out the simple approach first to see how it works. However, I do appreciate the advice.
That's exactly what I was thinking. Except I was just going to keep one boundry, and that would be around the players character. Anything that is not within the players boundry will simply be ignored and not do any AI. With the relative simplicity of my game this should work fine (there's no reason for monsters to roam around which aren't visible to the player). Is this the best approach, or are there other alternatives?
Raduprv:
I plan on making this for PDA devices. Obviously I'm new to this (hence the reason why this topic is in the For Beginners forum), and I'd like to keep things fairly simple for my first time (well, okay maybe not first game, but first PDA game). I don't want to add any needless processing unless I have to. I would like to have quite a few enemies on the screen without taxing the PDA more than I have to. If this simplistic movement scheme is too simple and the bots don't seem smart enough, then I will have to look into A* pathfinding. But until then, I'd like to try out the simple approach first to see how it works. However, I do appreciate the advice.
You would be surprised on how fast A* is, and how little CPU and memory it consumes, especially for relatively small distances.
In our MMORPG server we get maybe 50 path requests/second, PLUS the rest of the server stuff, and the whole server takes only like 15% CPU time on a P3 1100 MHZ (the path finding is about 1/3 of the entire server time).
The beauty of this is that you can easely extend your AI, map types, etc.
In our MMORPG server we get maybe 50 path requests/second, PLUS the rest of the server stuff, and the whole server takes only like 15% CPU time on a P3 1100 MHZ (the path finding is about 1/3 of the entire server time).
The beauty of this is that you can easely extend your AI, map types, etc.
A* is pretty good, one thing you should do, is make a little path module.
What it does, is it has a list of all the paths that need to be done, and based on how much of the path is completed, how long it has been since it was calculating that path, and its priority (whatever you want, how close it is to the player, ect.), it decides which paths to partially calculate, and how long to spend on them. All this is per frame, soit probably wouldn't be doing much, but it should give some nice paths without using up that much cpu power. (as well as having a few vaiables which determine how much time it has to play with, how much memory it has (so it could say only keep 20-30 paths midway, and not try the rest until one of the paths are finished. (so your not using up to many mb in paths, and nodes, and the trees.)
From,
nice coder
What it does, is it has a list of all the paths that need to be done, and based on how much of the path is completed, how long it has been since it was calculating that path, and its priority (whatever you want, how close it is to the player, ect.), it decides which paths to partially calculate, and how long to spend on them. All this is per frame, soit probably wouldn't be doing much, but it should give some nice paths without using up that much cpu power. (as well as having a few vaiables which determine how much time it has to play with, how much memory it has (so it could say only keep 20-30 paths midway, and not try the rest until one of the paths are finished. (so your not using up to many mb in paths, and nodes, and the trees.)
From,
nice coder
Author
Nice Coder:
Wow, that was actually informative. I've always wondered about that and A* pathfinding. That is, the player that the bot is tracking moves, thus the path needs to be redone. I guess that only makes logical sense, to have some sort of class to keep track of all the paths going on and when/if they need to be updated.
However, I am thinking of only having the bots track something they can actually see. Thus the original post I had still applies, since you technically don't need to pathfind something which is already visible. In general, it's just a straight shot. However, if the player goes around a corner, the bots would probably stop dead in their tracks. This may be something that's most likely not wanted, and the A* pathfinding routine would obviously come into play.
Anyway.. regardless. I think the logical step is to implement a line-of-sight pathfinding routine first (something simple like in my original post). I can then use that to build on by adding more complex routines, such as A*.
Wow, that was actually informative. I've always wondered about that and A* pathfinding. That is, the player that the bot is tracking moves, thus the path needs to be redone. I guess that only makes logical sense, to have some sort of class to keep track of all the paths going on and when/if they need to be updated.
However, I am thinking of only having the bots track something they can actually see. Thus the original post I had still applies, since you technically don't need to pathfind something which is already visible. In general, it's just a straight shot. However, if the player goes around a corner, the bots would probably stop dead in their tracks. This may be something that's most likely not wanted, and the A* pathfinding routine would obviously come into play.
Anyway.. regardless. I think the logical step is to implement a line-of-sight pathfinding routine first (something simple like in my original post). I can then use that to build on by adding more complex routines, such as A*.
Quote:Original post by Nice Coder
A* is pretty good, one thing you should do, is make a little path module.
What it does, is it has a list of all the paths that need to be done, and based on how much of the path is completed, how long it has been since it was calculating that path, and its priority (whatever you want, how close it is to the player, ect.), it decides which paths to partially calculate, and how long to spend on them. All this is per frame, soit probably wouldn't be doing much, but it should give some nice paths without using up that much cpu power. (as well as having a few vaiables which determine how much time it has to play with, how much memory it has (so it could say only keep 20-30 paths midway, and not try the rest until one of the paths are finished. (so your not using up to many mb in paths, and nodes, and the trees.)
From,
nice coder
Quote:Original post by wyrd
I have a question about the article in AI Game Programming Wisdom; Simple, Cheap Pathfinding (pg. 155).
In this article the author uses sensors/whiskers to detect whether moveable areas are near the bot and how close it is to non-moveable areas (including other bots). It does this by simply going through the pixels within and area and direction and detects whether or not it is the background color.
Anyway.. the problem I'm having is how to efficiently apply this to a real game. A simple game, no doubt, but a game nonetheless. In my particular game (as with any, I'd imagine), the background is not one single color. It is a bunch of 32x32 images are multitudes of colors, especially when overlaying another. A grassy 32x32 tile, for example, has more than 1 color in it (obviously).
I'm sure you're thinking "well, just mark each tile with a moveabe flag, simple." Right, but that's not the problem. That's a given when doing collision detection on map items. However, I'm not sure how to handle other bots in the game. If I loop through each individual bot to see if its within the radius of the sensors/whiskers, I'd have a highly inefficient collision detection system. 20 bots on the screen, each attempting to determine if each other is within the others sensor/whisker range, would be a 20x20 (400 total) loop. My math may be off (it might be less), but I think I make my point.
It comes down to this: How do I efficiently sense other moveable objects without having to go through tons of looping each frame?
Thanks in advance.
In regards to the example given - if you are not drawing with the alpha channe;, you could use that as the actual 'pixel color' instead of the magnitude of different pixels. Just an idea off the top of my head, what do you think?
Author
Not sure how that'd work since any given tile can have multiple color variations. Perhaps you could elaborate?
Addressing the original problem - as your game increases in size, the AP's advice of using bounding volumes is good (search in the articles section for BSP trees, Quadtrees and Octrees (although the Octree is really for 3D environments).
Sounds good to me. I've read that several games have implemented LOD for AI, which is basically what you're talking about - do less AI for things further away. For example, if a monster is a long way away it can either be totally inactive; or, of you want it to go somewhere, just work out how much time it would take to travel to the destination using a single algoritm (ie even as simple as straight line distance / speed) and then when that time has elapsed just update the monsters position (effectively it teleports). Doesn't matter to the player - they are never going to see it!
HTH,
Jim.
Quote:
That's exactly what I was thinking. Except I was just going to keep one boundry, and that would be around the players character. Anything that is not within the players boundry will simply be ignored and not do any AI.
Sounds good to me. I've read that several games have implemented LOD for AI, which is basically what you're talking about - do less AI for things further away. For example, if a monster is a long way away it can either be totally inactive; or, of you want it to go somewhere, just work out how much time it would take to travel to the destination using a single algoritm (ie even as simple as straight line distance / speed) and then when that time has elapsed just update the monsters position (effectively it teleports). Doesn't matter to the player - they are never going to see it!
HTH,
Jim.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
