In the previous article, I went over basic graph theory terms and concepts. Click here to read that article. In this one, I’m going to describe a game design problem I found while working on my project.
First, some background information on my project. Without going into too much detail, it involves two teams roaming a map killing neutral monsters as an objective. One of these neutral monsters I’m calling creeps or minions, similar to those in Defense of the Ancients 2 and League of Legends. In those games, minions align with a team and march down set paths and assault enemy structures on those paths. However, in my game, minions aren’t on a team, don’t attack structures, and have no set path. Here’s an early draft of the map I’m using:
Minions roam this map freely, and one challenge I’m facing is programming the minion roaming behavior. I came up with a number of ideas immediately. Here’s some of them:
- Just walk in some random navigable direction, changing direction if they run into a wall
- Create a bunch of paths and pick one to follow
- Pick a random target on the map and use Roblox’s pathfinding to do the hard work for me in finding a path to the point
Well, there’s going to be a lot of minions around this map. Maybe they’ll even travel in packs, who knows! I can’t have the minions raycasting for walls, and I can’t use expensive pathfinding for them to navigate. I also don’t want them switching directions a lot; I’d rather they travel a long path instead of small segments.
How did I apply graph theory to this problem? Find out in the next article.
