Archived

This topic is now archived and is closed to further replies.

FxMazter

pathfinding (advanced?)

Recommended Posts

FxMazter    164
Hello! When I was thinking about pathfinding and how to check where each character can go... I realized that the character will be bound to the size of the tiles right? If I walk to a wall and the wall isn''t taking a full tile... then it would be a gap between the character and the tile right? So I wonder if there is any other way of doing this so that the character won''t be bound to the tiles? The only way I thought of was to have an extra bitmap for the whole map. This bitmap would be of only black and white color, white for possible to walk on and black for not possible... But when making a big map like 10000x10000 pixels ... then this would take enourmus hdd space... like 100mb hdd space! (only the black&white bitmaps for 1 map... not to speak of all the other maps) Does anyone have any suggestion?

Share this post


Link to post
Share on other sites
Dean Harding    546
You can describe your world as a series of 2D polygons where characters can (or cannot) go. The polygons are overlaid over the tiles and are invisible to the user. Then you just use a more free-form path-finding algorithm to move around.

Another way would be to do your 1-bit bitmap, but on a tile-by-tile basis, rather than over the whole map at once. That''d save a lot of memory and you could even get away with using the alpha channel of the bitmap for this.

If I had my way, I''d have all of you shot!


codeka.com - Just click it.

Share this post


Link to post
Share on other sites
FxMazter    164
Ok, that last suggestion sounds very good to me... that one with saving the info in the alpha chanel. But if I am right that would only work with 32bit color right? (of course i could use tiles like you said.. but alpha chanel would be the ultimate sollution^^)

Well, then it comes to what picture format I should use? I mean... bitmap''s and jpg''s don''t support alpha chanel right?
So what format am I supposed to use to use the alpha chanel?

thx!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster   
Guest Anonymous Poster
all formats with 32bit color has an alpha channel..
Red = 8bit, Green = 8bit, Blue = 8bit & Alpha = 8bit..
btw...TGA support 32bit colors + they''re extremely easy to load/save

Share this post


Link to post
Share on other sites
directrix    181
I use the alpha channel to store collision detection data for my game, so I can do per pixel collision detection. Works very well, and looks very nice, although it's a little slower than doing line segments or rectangles. Anyway, I'm just trying to tell you that this is possible to do.



digital radiation

[edited by - directrix on January 29, 2003 7:13:34 PM]

Share this post


Link to post
Share on other sites
RatLord    122
I think you are worrying too much about everything working perfectly straight off. So what if a character cant walk right up to a wall? How often do you want them to do that? Good route finding will calculate the best path - and you will go there - when you are down to the final square handle anything that must be done in that square seperatley - for instance if a player is in one square have them route find to that square then move them to the players position.

Maybe a grid isnt the best option - maybe you should use waypoints. Go through the grid before the game actually starts and create way points for the accesable areas of your map. You can then also optimise by eradicating some waypoints - for instance down a straight narrow corridor you only need one at each end.

Look at first person shooters for instance.

If your bots have line of sight to the enemy they can move straight towards them - no route finding needed. If they have no line of sight they only need to route find until they do. This is simplified obviously. But u see what I mean?

Share this post


Link to post
Share on other sites