Jump to content
  • Advertisement
Sign in to follow this  
Kaloux

Pathfinding in 2d with bitmap collision file

This topic is 4079 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

Hello there ! I'm working on a (graphicaly speaking) Baldur's Gate like which looks better every day, but I have a problem with pathfinding. Actualy, the game is composed of : - a background image (pretty large, bigger than 2048/2048 at 1280/1024) - a collision bitmap (as large as the background) - a player you can move by right clicking on the background Right now, the collision bitmap is only used to set the final position of the player. If I click on a surface that is not walkable, the game returns me the closest walkable position (and it works pretty well). But my character is running through the walls... So I decided to implement pathfinding. I read several articles over the net (especially this one : http://www.gamedev.net/reference/articles/article2003.asp which taught me the basics), but couldn't find what I was searching for. In fact, afaik, A* is designed to work with tiles or grids, not with single pixel nodes. Well, it could be made, but with a very large bitmap it would eat up way too much memory I think. I thought I could add a parameter to my "getShortestPath" function that would rule the "precision" of the calculation. It would be set to 4 by default, reducing the virtual size of the collision map by 4 and so dividing cpu used by about 4 also. Do you know any other method that would fit best to my situation or will I have to write my own A* algorythm ?

Share this post


Link to post
Share on other sites
Advertisement
A* is just a graph search algorithm. There are simpler algorithms you could use, such as iterative deepening. There's a post from a while ago where someone recommended iterative deepening A* because it's a lot easier to implement than A* and in most sitations almost as good. The search algorithm is entirely orthogonal to the space being searched. As long as you're doing graph based pathfinding you'll run into the same issues with choosing where pathing nodes should be and how densely they should be placed.

You can also place pathing nodes by hand (or alternatively, write a program to automatically place them). I think you are describing an implicit description of the pathing nodes. Instead of explicitly defining their positions, you are saying that they are every pixel where the x and y value are a multiple of 4 and the pixel is walkable, and they are connected to nodes where the x or y value is at a distance of 4. An explicit definition of the nodes would describe their positions and their neighbors. With a sparser graph, you'd also want to implement some algorithm for walking to and from the nearest node and possibly path smoothing.

A* and other graph search algorithms are designed to work on any graph, not just tiles, grid cells, or pixels. Those are just special cases that might admit certain optimizations.

Share this post


Link to post
Share on other sites
In this static world you're building, I personally think it would be best to just pre-define set paths through each map, like a network of roads essentially. When your NPC has to move you would then have it search this weighted graph for the shortest path from where it's at to the destination node/position. Good algorithms for this would be Dijkstra's or Bellman-Ford's algorithm.

If you need to be more accurate than that, or if there are dynamic obstacles in your universe, then look into iterative depth-first search, as Vorpy mentioned. A* really can't be used unless you have a heuristic function that can estimate the cost of reaching some goal state where the costs vary between different nodes; otherwise if cost is uniform then all you're doing is just breadth-first search.

[Edited by - Omega147 on April 20, 2007 8:42:05 PM]

Share this post


Link to post
Share on other sites
Yup, I use (almost) the same heuristic as the author of the article I linked in my first post, "the Manhattan method" (only difference is that I don't *10 because of the high number of node that can separate the origin point and the destination).
I can't test what I did ("tried to do" would fit better) yet, I still need to manage which path has to be chosen and tell the program to "go backward" when a node leads to nowhere.

That was less complicated than I firstly thought :)
...assuming what I did actualy works :P

About pre-made paths, I don't think it's a good idea : it would make the game pretty much... rigid or unflexible.
It could be fine for NPCs as the player doesn't control them, but for the player's characters it doens't sound good to me.

For now, I will continue my work on A*, and if it eventualy doesn't fit my needs, I'll go for iterative deepening ;)

Thanks for your answers !

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!