When we designed the prototype for Party of Sin, we had very basic enemies. They would move towards the player and shoot if there were no obstacles in the way. If they ran into a wall, they would get stuck. We knew that in the final product we would need pathfinding as well as smarter, more interesting, and more challenging enemies.
The first AI step was to implement pathfinding; i.e. how to get around the level. Traditionally, video games use the A* algorithm, which consists in using a graph to finding the shortest path from a node to another.
We started by building a graph that the AI would navigate. There was a connection from a node A to another node B if an AI actor was supposed to be able to get from A to B. There were three types of connection: walk, jump, and ladder. To go from a location to another, the enemy would find the node closest to itself and the node closest to the target destination, then use A* to find the best path. As the levels got bigger, we noticed that it was becoming very tedious to build the graph; there were too many nodes.
That’s when Dan came up with the idea of getting rid of all the walk connections; we would use nodes as one dimensional space instead. We would assign a ground identification, or GID, to each platform. If two platforms had the same GID, then an enemy could move from one to the other by walking left or right. Platforms became the graph nodes, and platforms with the same GID represented the same node. AI agents knew which node they were at by checking the GID of the platforms they were standing on. Now that we didn’t have walk connections anymore, we added fall connections that would allow enemies to go from a platform to another by walking off its edge. With this simpler implementation, the AI graph contained a lot less nodes, and it was considerably easier to build it in the map editor.Problem one was solved; no more getting stuck into walls. Ground enemies could chase the player all around the level as long as the AI graph wasn’t flawed.
2. Order System
The second AI step was to make combat more interesting. At this point, the enemies would relentlessly chase the players and shoot them if they were in range. This was boring and predictable behaviour. Combat was too simple; it had to get more challenging. One thing we tried was to increase the number of enemies. The game did get harder, but it was still not very exciting. We then thought of making each one harder to kill instead of spawning more of them. Increasing their health points made them more resilient, but they had to be smarter as well. We also wanted to diversify their behaviour to make fighting them more interesting. For instance, some angels would be aggressive and charge at you, while others would be more careful and pull up a shield to protect themselves from projectiles.To answer this problem, we came up with an order system which has three kinds of orders: idle, combat, and atomic. Idle orders define how an AI agent behaves when there are no enemies nearby. They can guard a position, follow a buddy, or patrol between two points. Combat orders specify what an enemy does when it finds a hostile target; it contains all the battle logic and makes use of atomic orders. For example, the charging angel combat order states: attack with the sword if the target is in melee range, shoot an arrow if the target is in shooting range, and charge the target otherwise. Atomic orders are very specific actions that the AI enemy performs such as swinging a sword, shooting a bow or pulling up a shield.Each AI actor has an idle and a combat behaviour. It follows the idle order until it finds a target. As long as a target is in sight, the enemy will keep executing the combat order. If it doesn’t see a hostile target for more than a given period of time, it reverts to the idle order.
3. Timing component
When we played other platform games such as Mega Man and Super Mario Bros, we noticed that timing was an important part of gameplay. We introduced a charging and recovery time to the atomic orders. Basically, charging time is the time between which the enemy shows that it is going to perform an action and the time it actually performs the action. Recovery time specifies how long an enemy is vulnerable after executing the action. For example, an angel would pull back an arrow on his bow for two seconds before shooting, and wait one second before executing its next order. This allows the players to dodge enemy attacks more easily, and to damage them while they are recovering.
4. What’s next?
We still have to work on pathfinding for flying enemies. They could follow the AI graph we set up for ground enemies, but then they wouldn’t be making optimal use of their flying capacities to find the shortest path. Since they aren’t affected by gravity, the situation becomes similar to top-down game pathfinding. We were thinking of using an AI mesh. We also brainstormed other behaviour ideas such as teamwork and leadership. Charging angels could cooperate with others to rush the players from all sides rather than come at the Sins in a line, or archer angels could take cover behind shield angels. This is all work in progress.
I found this very useful as a programmer however I find that your node pattern is not logical to someone using your editor. I would personally prefer the previous as it's more logical to a designer. Of course you've used it more so do you find that the previous method is more logical just more time consuming to create?
It takes about 10x longer to create and connect all those nodes. In a small level, it's not so bad, but as the levels get bigger it is impossible to maintain. We have created a script to automatically group platforms into GIDs by analyzing the shapes, and this saves us considerable time. All the designer now has to do is point out where the jumps and ladders are located.
This is not to mention the huge performance benefit of having a much more shallow search in the A* graph. Using a GID as a one-dimensional space where an AI can get anywhere on it my moving left/right has been a huge optimization.
Whoa,you are seriously interested on this game!Nice job,I hope you all of the luck,and happy easter for everybody :D