Not logged inGosu Forums
Forum back to libgosu.org Help Search Register Login
Up Topic Gosu / Extending Gosu / Path finding library
- - By zombiecalypse Date 2014-06-12 15:29
Hi, I was revisiting a game I created (2D RPG) and started extracting some code. I present to you:

Chingu Pathfinding

* Gem
* github

It's some reasonably optimized C++ code that finds the shortest path on a static map.

To install it, run

gem install chingu-pathfinding, which requires a c++ compiler.

From the documentation:

Initializing the pathfinder

The scenario this library assumes is that there is a rectangular area, where some pixels are blocked.

Optionally you can set a 'block_size', so that not all pixels need to be checked. This leads to suboptimal results and blocky moves however, but the better performance might be worth it.


class Map < Pathfinding
  def initialize(width, height)
    super(width, height, 5)
  end

  ...
end


initializes the map to have a block_size of 5, which means only about half of the pixels needs to be checked.

class Map < Pathfinding
  def initialize(width, height)
    super(width, height, 1)
  end

  ...
end


gives a map, that doesn't use bigger blocks at all.

Implementing the blocked?(x, y) method

The method must return false if the pixel (x, y) can be walked over and true otherwise. So basically if there is a wall, it should return true and if there is nothing it should return false.

class Map < Pathfinding
  def initialize(width, height)
    super(width, height, 1)
  end

  def blocked?(x,y)
    x < 10 or x > 90 or y < 10 or y > 90
  end

  ...
end


would be a complete (albeit boring) setup for the pathfinding.

Using the path finding methods

When in doubt, call find_path(start_x, start_y, goal_x, goal_y), which will return a list of points (arrays of 2 elements) to pass through with the first points being [start_x, start_y] and the last being [goal_x, goal_y]. If you move linearly between the points, you will not hit any blocked pixels. If you can't reach the goal for some reason, nil is returned.

There is a second path finding method: find_path_update(start_x, start_y, goal_x, goal_y, path) This uses the observation that if we move along the path and maybe the goal moves a bit, then it would be wasteful to throw the previous ideal path away. If your map is big enough it might be worth to use this instead of using find_path for updates on the path finding.

It's probably buggy as hell, but if you don't want to implement pathfinding yourself...
Parent - - By jlnr (dev) Date 2014-06-12 16:21
Nice interface! Does this have any connection to Chingu, though? Looks like you might as well use it with Gosu, Gamebox or even in a Rails webgame %)

Edit: I also wonder if it would be worth it to change the find_path method to return a linear array of coordinates ([x1, y1, x2, y2, ...]) to take a big load off the garbage collector. But I think working with such an array would be quite painful. :/
Parent - - By zombiecalypse Date 2014-06-12 20:10
Thanks! It doesn't really connect to Chingu in any way, so you can actually use it with any platform and library where you can execute native code.

The thing about taking some load off the gc could be true, I'd have to run some more realistic benchmarks to gather if this is a problem.
Parent - By shawn42 Date 2014-06-16 20:55
Nice.

I wrote something similar in pure ruby a while back: https://github.com/shawn42/polaris

I always meant to revisit and add some things like jump point search..
http://gamedevelopment.tutsplus.com/tutorials/how-to-speed-up-a-pathfinding-with-the-jump-point-search-algorithm--gamedev-5818

Keep up the good work.
Up Topic Gosu / Extending Gosu / Path finding library

Powered by mwForum 2.29.7 © 1999-2015 Markus Wichitill