Tiny Dungeons – Steering and Pathfinding

I’ve spent a few hours today and yesterday adding behaviour to the hero and monsters. The biggest challenge is keeping monsters apart, having them follow the hero and not tunnel through walls.

For path finding i use a rather simple and unoptimized implementation of A* on a tile grid (though it’s generic enough to work on any graph really). Path finding is only used to guide the hero to the point on the map the user tapped on.

For keeping monsters separated i give them a simple separation steering behaviours. To avoid walls, i implemented simplified obstacle avoidance which exploits the fact that the entities are moving on a tile grid. The monsters follow the hero by simple seeking. Those three steering behaviours (separate, wall avoidance, seeking) actually make for a passable overall experience. Each steering behaviour has a weight, so i can control the contribution of individual steering behaviours to the overall direction a monster takes. E.g. wall avoidance is weighted higher than seeking or separation. This (kinda) guarantees that monsters will prefer overlapping with each other more than tunneling through a wall.

I tried doing A* for every individual monster, but wasn’t happy with the result. Steering behaviours can’t resolve deadlocks resulting from paths that overlap in space and time, which creates stalemates among monsters. There might still be a way to make this work, however, for the simple dungeon maps the seek behaviour should suffice.

There’s a nice paper by Vavle on how they solved similar problems in Left 4 Dead. It’s a bit overkill, but some principles i could apply to my scenario as well. Haven’t had time to look into it yet, reactive path following looks pretty much what i had before i killed A* path finding for monsters. Thanks to Dave (@redskyforge) for pointing me at the presentation.

Here’s the obligatory screenshot, green lines show the velocity/direction, red lines show the steering force/acceleration. Blue tiles are the path nodes the hero follows.

You can try the desktop version here. Press ‘d’ to toggle the debug renderer.

You can try the Android version here. Alternatively you can use this QR code:

  • http://www.chrismweb.com ChrisM

    Pretty cool swarming behavior! It worked well for me, and monsters only had their head under the top blocks sometimes.

    The guy will probably need some kind of “zelda like” charge up and swing around in a circle move, to kill a bunch of them at once.

    And hey- upgrade/IAP- further sword cutting radius ;)

    Looking good-

  • Ray

    Looks nice! Further than my group of friends has ever gotten on a game project… You actually have something rendering a scene with things moving around on it :)

  • BahnhofKoffer

    looks good and works great on my Sony Xperia Pro.

  • http://www.teamblubee.com blubee

    Badlogic very nice. I was actually working on something like this for a project I was doing although much simpler.

    I like the art style *high five to orangepixel for that*
    I like the demo, that shader you got in there for the ligh gives it some real nice atmosphere. Here’s to you pushing this one through to completion!

  • Silverwolf

    Looking cool.

    A big skeleton group hug. I notice no joystick implementation, so will really feel like a phone game. Are you going to use finger swipes for sword attacks?

    Good luck on it.

  • Milo

    This looks awesome. I particularly like the lighting! Is it possible this could be released (in some form) as a tutorial/example code? I’ve been looking to take the jump from 2D into 3D and this seems like a perfect stepping stone.

    Good work!

  • http://zanardiliza.com Leonardo Zimbres

    Mario, this game rocks! Loved every bit of it.
    After working on a good book and excelent framework, you surely deserves a good game on your portfolio.

  • João Neto

    OpenSteer is a good C++ library for steering behaviors in autonomous characters.
    http://opensteer.sourceforge.net/
    This could be a great addition to Libgdx, the same way that Box2D was.

    Think about it, and thanks for your great work.