A Traveling Salesman Walks into a Bar…

Work has steadily continued on Suzy’s AI, and it was necessary too. As she was at the time of the last post, she would have been absolutely no challenge to the player. I could have just allowed her to cheat, knowing where all of the fruit objects were and used some form of random number generation to decide if she ‘found’ one or not. That is the approach that some games take, and I suspect that many indie developers would have done just that. I can’t blame them; creating AI with any amount of intelligence is very hard. It would be very easy to do that and move on, especially if you are an indie developer who is building a commercial game. But, I absolutely will not take this route. The whole point behind this entire project is to get experience and gain knowledge about making good AI. Did I think about giving in? Yes. I have thought how much easier it would be many times, but again, that would be missing the point of this project.

So I asked myself how I might go about searching for these fruit objects, or any objects, in an environment as large as a tropical island. The first thing I would need to do to search effectively is to orient myself in my surroundings by finding some landmarks so that I won’t get lost. Aha! I can have the AI travel to landmarks that are all over the islands. By doing this, it will also give the appearance that Suzy really is using some form of intelligence to perform this search. If the player watches her, they will notice that she is traveling to a location that has a very distinct landmark. Hopefully this will feel fair to the player, as they too can orient themselves by using these landmarks. Moving Suzy around the island isn’t that difficult with the custom EQS generator that was made specifically for this purpose. But, how exactly should the AI chose which landmark to visit? And how should she go about visiting each one? I chose to have her randomly select a landmark to visit, but I didn’t want her to visit the same landmarks over and over without going to each one first. That was important to me, because it would then feel more like she really is searching, rather than just randomly running around. To implement this, I chose to use the “Traveling Salesman” approach for visiting each location.

The idea behind the traveling salesman approach is that the ‘salesman’, Suzy in our case, will travel from her starting location to each of the destination points, or landmarks. But, she will not backtrack to a previously visited landmark. She will only go to unvisited landmarks until all of them have been visited. Only after all of the landmarks have been visited will the AI be allowed to revisit a landmark.

Once at the landmark, I wanted Suzy to give the place a good search. So how did I implement this? The same technique that was used to move her to the landmark: Traveling Salesman. I actually implemented this first, so that I could make sure that it would work the way that I wanted it to. Once she arrives at the landmark, the behavior tree task generates a random number of points within a range that can be set in the behavior tree. For this, I felt that 3-6 points around the landmark would be fairly good, but the range can be set between 2-8. Once these points are generated they are handed off to Suzy’s behavior tree so that she can run these points, utilizing the traveling salesman approach. It gives Suzy a nice appearance of being an excitable little monkey that is running around trying to find these fruit objects.

While Suzy’s AI still has some work to do before she will be challenging enough to make this game fun, I think that I am close having the developmental part done. If I can just make this a little more successful at finding the fruit objects quicker, it will just be a matter of balancing the numbers to get things just right. I hope.

Leave a Reply

Your email address will not be published. Required fields are marked *