Sign in to follow this  

Simple, Cheap Pathfinding (from AI Game Programming Wisdom)

This topic is 4728 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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*.

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

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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).

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.

Share this post


Link to post
Share on other sites
Quote:
Original post by wyrd
Not sure how that'd work since any given tile can have multiple color variations. Perhaps you could elaborate?


Quote:

... It does this by simply going through the pixels within and area and direction and detects whether or not it is the background color.

...the background is not one single color. It is a bunch of 32x32 images are multitudes of colors, especially when overlaying another...


What I am suggesting is apply the techniques that you described, but use the alpha value instead of the pixel color - this is only possible if you do not draw with the alpha. You said that it simply goes through the pixels within an area and direction and detects whether or not it is the background color. Instead of using the background color - test it with the alpha value - which you would have set manually. This way, you are only working on a scale of 0-255 and since the image is not being drawn with the alpha, the values do not matter. I will try to illustrate it with words a little better:

Let's say you have a 32x32 grass tile. It does not use the alpha value of the pixel components. You can set the alpha value for all pixels to 0 for full passability and no objects are there. Now, since you are using layers - everytime you check for passability you will be adding up all the layer's alpha values. Since they are all 0 currently the tile is passable and can be moved onto freely. Now this will start to get more complext, but I hope I do not lose you. Now, lets skip over the fact that some tiles may not be passable by nature - such as water - and move to characters. If you set the alpha value of them to lets say 1, you will noe be able to check to see if a set of pixel's has a collision. If we have 5 layers of free grass - it is 0 + 0 + 0 + 0 + 0 = 0. Then, an enemy moves there, so some pixels are now 1. When you are doing the collision checking, if the result is 2, then you know there was a collision between 2 bots at some pixel point.

Can you see what I am saying now, or do I need to exaplain more? This is all theoretical - I have not ever tried this method, but I would think that it would work - as long as the sensors/whiskers method you are describing using background colors works.

Share this post


Link to post
Share on other sites
Ahhh I see what you're saying. Yes, that does make sense. I'm not sure how to check the Alpha channel, but I'm sure it wouldn't be too difficult to access it.

Share this post


Link to post
Share on other sites
Quote:
Original post by wyrd
Ahhh I see what you're saying. Yes, that does make sense. I'm not sure how to check the Alpha channel, but I'm sure it wouldn't be too difficult to access it.


Me either :/. I know in SDL, it has a SDL_Color that has a Unused (assumed alpha) item along with the r,g,b values, so that's what I was thinking of when I said this. Now for other libraries, I'm not too sure either, but I bet you could find it out fairly easy.

Share this post


Link to post
Share on other sites
I'm not called Nice Coder for nothing, you know! (ask away, if you have questions)

You should be able to get it to repath without having to recalculate the whole thing. (you loose optimality tho)

Change the heuristic to account for the updated position.
reapply the heuristic to everything in the open list, resort
And keep searching where you left off. (thats why you always have a path-manager, it can speed things up a LOT).

you can also have the agents start moving the frame they ask for the path. just expant do maybe 5ish nodes, grab the best one, and start following, then pass it the the memory manager, keep walking the best path as it comes out, and by the time he goes 5 steps he'll have a full path.

This helps if you've get a LOT of agents (HUGE > 100K) needing paths simultaniously. You'd just get them moving in the most promising direction, and try to sort out there paths in the second(s, if you have a gigantic number), that follow. But by using your path-manager, you can get the ones that matter most the paths first, so it seems a lot better.

Its not as slow as some people think, and it can be quite nice. (its also good to have one, once you start making bigger games)

If your working on pda's, you should start to make games w/ time limits for different things.

So per frame, physics can have 100ms, graphics can have 200ms, ai can have 100ms, ect. but they all pick up where they left off. This allows you to have things which would require a few seconds being spread that thin that nobody notices.

From,
Nice coder

Share this post


Link to post
Share on other sites

This topic is 4728 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this