I absolutely love the MegaMan series. For the purpose of this article, I am going to be talking about the classic megaman series, although I love the X series as well. One thing that that has always been boring to me over the years is that as time has gone on, the AI in platformers such as the Megaman series as pretty much stayed the same. I feel like enemies come in a few forms.
- Completely Stationary
- Moving left and right on platforms, and sometimes jumping vertically
- They follow some set pattern, or operate in a complicated way, but only in a set area (Robot Masters)
Anyways, this just got me thinking, how hard would it be to create a AI system that could successfully navigate classic Megaman levels?
Megaman Classic levels are primarily made up of tiles.
There are no slopes, so this ends up creating a fairly simply array of data.
- Solid Tiles (Walls, Floors, Ceilings, Lava/Spikes/OHNO)
- Open Space
So, how do we make an AI that can traverse this stuff? By creating a navigation mesh! A navigation mesh is simply a data structure that dictates where the AI can go. For example, if there is a solid tile with a open tile above it…that means the AI can stand there. If we apply that to our example room, we get this.
These are Navigation Mesh nodes. Nodes can be connected to other nodes to tell the AI what it can and can’t travel to. Node connections are one way, and should contain information about the method of travel needed to get from one node to another.
Lets see if we can figure out rules to connect these nodes together!
The walking rule
If a node is walkable, and the node to its left and right is walkable, the AI can walk to that node. Simple enough. Now this means our AI is aware of platforms. Now are navmesh looks like this!
The jumping rule
Now this is where things get complicated. How can we determine what the AI can jump to! Lets use a simple example to settle this one. Blocks of stairs.
If a node is walkable, and the node next to this node isn’t, look at the node above that one. Continue until you hit JUMPHEIGHT nodes, or find a walkable node. Now, we have found a place we can jump to! And thats fine, right? Nope! Check out a modified map, and you can see how this algorithm fails.
See, we forgot to see if our little Megaman would hit his head! We not only need to check the path in front of us, but the path above the character. So now we are good, right? NOPE.
A one block gap. Our AI has no clue what to do here. It has reached a challenged it is not equipped to beat. So, we need to write a function that uses our AI’s movespeed, jump height, and fallspeed to determine if it can physically jump to a block.