Graph Theory in Roblox (Part 2 – A Problem)

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:

An early draft of the map (not final). Notice the navigable paths through the map. Click to view the full image.

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.

Author: Ozzypig

Roblox developer and computer scientist. I love all things coding and game design!