Two additions: BSP dungeons and A* pathfinding

As I blogged about a couple months ago, I’m writing a little RPG for a fun hobby project. I was inspired by this twitter thread about a random monster generator, and I designed a tabletop rule system to use. Since then I’ve been implementing things in Unity, and this month I want to talk about the first two things I programmed: procedural dungeon generation, and grid-based A* (or A-star) pathfinding.

In addition to randomly generated monsters, I wanted this game to have randomly generated dungeons. Here’s a video showing what I came up with:

I used binary space partitioning (one of a number of proc-gen techniques useful for dungeons), with my code based on this: https://github.com/rombdn/unitydungeonbsp

That open-source generator provided the map data, but I still needed to build the mesh as described in this old tutorial of mine:
https://www.raywenderlich.com/82-procedural-generation-of-mazes-with-unity

---

As for A* pathfinding, here’s a library for and demo of A-star on a 2D grid:
https://jhocking.itch.io/astar-pathfinding

Many years ago I had programmed a pathfinding library in AS3 to use in Flash, and I decided to port it to C# for use in Unity. Click and drag the green and red squares in the interactive demo to see the pathfinding algorithm in action.

For many games (especially 3D games) you would be better off using the NavMesh pathfinding built into Unity, or you could use the A* Pathfinding Project. However those approaches aren’t great choices for a simple 2D grid, plus this library is a good reference for you to learn how A* works.

I relied heavily on this tutorial when I was learning the algorithm:
https://gist.github.com/jcward/45afd22560939aaae5c75e68f1e57505

NOTE: That tutorial uses Manhattan distance for the heuristic value, but my code uses squared magnitude instead. I made that change because squared magnitude is still pretty fast to calculate and is more accurate, giving a slightly different (and better I think) resulting path. I left Manhattan distance as a TODO comment in the code if you want to try that instead.

• Uncategorized