The collider (wall) grids are represented as a tiny green bamboo stick (not clearly visible though) and the nodes are where those blue lines are connected. I did not pay attention but as I write this article, I realize that it still generates redundant connections and can use some optimizations, even though it's not so critical to the system performance.

​

Talk about storage, I store all information about node coordinate and their adjacent nodes in a combination of nested List and KeyValuePair, it looks like this:

​

List<KeyValuePair<Vector2, List<KeyValuePair<int, float>>>> Nodes;

​

The main list stores all nodes information. Each entry of that list contains pair of information. The first one (the key) is a Vector2 which is the path node's coordinate. The second one (the value) is the secondary list, which stores adjacent nodes. That secondary list also stores a pair of information. The first one (the key) is the index of adjacent node in the main list. The second one (the value) is the cost (distance) between the main node and the adjacent node, I did this for optimization purpose so that I don't have to recalculate the distance over and over again. I know it's not the prettiest of all, but I kinda like it that way.

​

C. Path Generation

The data structure is done. Now it's time to make the sortest path generation algorithm. The first thing to do is to find the best starting node around the actor. Since closest node alone will not always produce the closest path possible, so I have to take orientations between nearby node, the actor, and the target point into account. I want to paste the code here, but unfortunately Wix doesn't have the feature to easily paste code snippets. The snippets above were manually customized and colorized by me. It's fine as far as it's no more than two lines long, but definitely no for a whole block of a method! But as exchange, I have attached the script file for both the AI and the path finding system at the bottom of this page.

​

After deciding the starting node, I continued by making a recursive function to generate a sequence of nodes until the destination point is reached. To do that, I iterate all adjacent nodes of the current node and try to guess the best next node. The evaluation I use is pretty similar with how I decide the starting node: by calculating the distance and factoring the orientations. The only difference is that now I don't have to shoot a raycast because the node and graph generation already did that out of the box. When the next node is decided, I store the current node into the sequence and set the current node to the next node. And then keep repeating the process until a node can be directly connected with the destination point (uses raycast). Keep in mind that to evaluate the next node, we have to makes sure that the evaluated node isn't already registered in the generated sequence, so that we won't go to the previous node back and forth.

​

I know, normally people will try to generate multiple paths and then evaluate which one has the absolute lowest cost. But here I'm trying to make a blazing fast path generation that only needs one-time iteration and still produce a highly reliable sort path. And my evaluation method seems to work pretty nicely.

​

D. Path Optimization

And I'm still not done yet with this generation stuff. I still need to optimize the generated path to make it even shorter. Here I'm evaluating each node in the previously generated sequence and try to skip some nodes if possible, by shooting raycasts between nodes in the sequence. But to do it properly so that the optimization doesn't produce weird path, it should be staged into 3 sub-phases.

​

The first phase is to decide the last node. The current last node in the sequence isn't always be the best one yet. So we will try to find an even better one. It's done by iterating the nodes in the sequence descendingly starting from the last node in the sequence and shoot raycast from the destination point to the iterated node. If the ray hits an obstacle, stop the iteration and set previously iterated node (the last one that doesn't have obstacle between it and the destination point) as the last node. Then we can move to the next phase.

​

The second phase is to decide the better starting node than the first node in the current sequence. It's also done by iterating the sequence descendingly, starting from the new last node from the previous phase. As soon as we can shoot a raycast from the iterated node to the starting point without hitting any obstacle, we stop the iteration and set it as the starting node. Then we can move to the last phase.

​

The last optimization phase is trying to skip nodes between the new starting and last node. Unlike before, we iterate the sequence ascendingly. But the basic idea remains the same: shoot a raycast and skip nodes if they don't have any obstacle in between.

 

Writing highly optimized code for it is very tricky. But I have to make it excellent because this function will be used very frequently and intensively. And I did just that! In the end, the test proves that it only takes staggering 0.003 ms for one path generation on my PC. It's probably able to handle hundreds or even thousands of path generations at once without any noticeable performance drop!

 

I know that others will recalculate (regenerate) the path every certain interval, yet for now I'm reluctant to do that for performance reasons. And all of those path node and path generation things are handled and stored in the server. So it will not stress the client's (phone) device at all.

​

E. Implementing Path Generation to the AI System

Implementing the path generation system to the AI movement was not easy at all. First, at that point they use a direction and step count based movement, which is very basic and isn't compatible with the path finding system. And not only that, the movement in server- and client-side wasn't synchronized at all. So I have to spend some times learning how they handle the movement and make necessary modifications to make it synchronized.

​

F. Order Queue

After that, to bridge between the per-step based movement, I made an order queue system. The system will keep the actor moving until it reaches the destination point, then continues with the next point and repeat until the final point is reached.

​

After it's done, I can finally implement the path finding system to the AI's movement. To do it, I passed the sequence produced by the path generator to the queue system, as simple as that. Then I made a simple script ordering the AI to move around the arena, and the result was really pleasing to see: they were able to avoid walls and obstacles! Finally!

​

G. Improving the AI behavior

The movement part is finally done. The next thing to do is to make the AI able to play quite competitively and gives some challenges to the player. I find it's hard to explain this part. But basically, here's what my AI script is capable of:

​

• Path finding and obstacle avoidance

• Evaluate a better nearby target

• Retreat and hide when low on health

• Help each other

• Gang on stunned enemy

• Aggro on attacker

• Revenge on killer

• Accepts commands from player (stick together, retreat, ignore power up, spread out, etc.)

• Acquire healing item when needed

• Use special skills and aims properly

• Displays their current state in form of chat message

​

I feel like to make the AI even better but the others were afraid that it will make the game too hard for new players so I rescinded the plan, since it's competitive enough already anyway.

 

I think that's all I can describe about the AI making part. There was obviously a lot more than that. Not everything went as smooth as what I tell above. It took me roughly one week to finish the AI and move on to my next task. Anyway, here's a small undocumented video previewing how the AI (system) works. Thanks for reading and see you in the next chapter!