I notice that I always push off AI as long as possible. When I inevitably start working on it, it becomes one of the most rewarding and frustrating aspects of game development. For Knighthood I wanted to have a (decently) smart AI that could actually follow you around the map instead of ping-ponging between platform edges waiting to be attacked.
The world's most boring ping-pong match.
| I decided to go with a node system and an implementation of the A* algorithm for the character pathfinding. I wrote a tool in Unity with modifiable settings (jump height, allowed drop horizontal distance, etc) that helps me procedurally create the Nodes on each platform and then bake the Node's connections with its neighbors. Currently it only works for AABB's (Axis Aligned Bounding Box) but I plan on upgrading it after making sure the pathfinding works well. |  Day 1: First version of a Point Graph. Orbs are Nodes, lines are the connections, and characters can fall/jump through the dark platforms. |
 Day 2: The blue lines represents the characters chosen path to its destination. | After my second day of working on it, I had successfully implemented A*. Although I had to tell the enemy where to start and it's goal, it could find a path (if there was one). My next challenge was trying to quickly find the start and end Nodes. To solve this, during the baking process, I break the world into a grid and save references to all of the Nodes in each grid space. Using this method I can get the list of the closest Nodes and only have to check them to see which one is actually closest to the target position. If a space doesn't have any Nodes in it (ie the character is in the air), then I check the grid spaces surrounding it. |
| To get the correct grid space we have to do a little math. Say each grid space corresponds to a 5x5 chunk of the world and we have a 4x6 matrix. This means the grid covers from position (0, 0) to (30, 20) (x and y are different in position vectors than matrix indices). World Matrix (00, 20) (30, 20) [0,0] [0,1] [0,2] [0,3] [0,4] [0,5] [1,0] [1,1] [1,2] [1,3] [1,4] [1,5] [2,0] [2,1] [2,2] [2,3] [2,4] [2,5] [3,0] [3,1] [3,2] [3,3] [3,4] [3,5] (00, 00) (30, 00) |  Day 3: World Matrix. |
Ex: Character is at x: 23 y: 16 what grid space is he in?
x = 23/5 = 4 (divide by grid space size and drop remainder)
y = 16/5 = 3 → 4-1-3 = 0 (you have to invert the y)
(position (x, y) equals matrix index [y,x])
(23, 16) → [0, 4]
x = 23/5 = 4 (divide by grid space size and drop remainder)
y = 16/5 = 3 → 4-1-3 = 0 (you have to invert the y)
(position (x, y) equals matrix index [y,x])
(23, 16) → [0, 4]
Day 3: Enemy can track player decently well.
Currently the enemy can constantly track the player around the map, including jumping and falling through translucent platforms. My approach still needs a lot of work and optimization but I think it's a good starting point. The hard part is going to be passing this info to the character controller and motor. But that's another post. I hope you enjoyed my first post, I would appreciate any feedback for the blog or my pathfinding solution. You can comment on this post or contact me directly. Thanks!
RSS Feed
