Simple, Cheap Pathfinding (from AI Game Programming Wisdom)

Started by
12 comments, last by Nice Coder 19 years, 3 months ago
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.
Advertisement
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.
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.
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
Click here to patch the mozilla IDN exploit, or click Here then type in Network.enableidn and set its value to false. Restart the browser for the patches to work.

This topic is closed to new replies.

Advertisement