Finding the Good Injection Point in Project Hoshimi (Part 2)

• Download source - 962 B

Introduction

Project Hoshimi is a part of the Imagine Cup challenge. Imagine Cup is the world's premier technical competition for students. In 2006, more than 65,000 students from 100 countries participated, leading the competition to be dubbed the "software development Olympics".

In Project Hoshimi, you will have to create a strategy for a team of virtual "nano bots". They move inside a map (representing a part of the human body) and they score points by doing some actions (such as collecting AZN molecules). Then, your team will have to fight against other teams, on given maps. Like in a video game, you can watch the games using a 2D or 3D viewer. The difference is that you cannot interact with your bots during a game. You have to develop the whole behavior of your bots before you launch the game.

You can download the Project Hoshimi SDK here.

Abstract

First of all, I wish you a happy new year, and I wish you to go to Korea!

For the first part of this article, I explained a simple method to compute your injection point. Now, we will look at a more complex method. This article requires some basis in mathematics.

Here We Go

The goal of this method is quite simple: we will rate every cell in the map. The cell with the best rate will be your injection point. The big deal is to define the way you will rate each cell.

The idea is to give a good rate to cells near to a Hoshimi Point, an AZN point, and a Navigation point. To do that, we will use a 2D-Gaussian function:

This function is very useful in statistics. For more information, take a look to this Wikipedia article.

We will apply this function to every interesting point. In our example, we will only consider AZN and Hoshimi points. It's your job to find what is an interesting point.

Let's first write a function that find the best rated cell:

public Point FindInjectionPoint()
{
    double[,] rates = new double[200, 200];

    GiveRates(rates);

    Point bestPoint = new Point(100, 100);
    double bestRate = -1;

    for (int i = 0; i < 200; i++)
        for (int j = 0; j < 200; j++)
            if (bestRate < rates[i, j])
            {
                bestRate = rates[i, j];
                bestPoint = new Point(i, j);
            }

    return bestPoint;
} 

This function is quite generic. Its purpose is to find the best rate, according to the GiveRates function. GiveRates has to populate the array given in parameter with the rates.

The Gaussian Function

Now, let's define this Gaussian function. A Gaussian curve has 3 parameters: an intensity, a center, and a spread:

A is the intensity. It is the value given to the center of the Gaussian. (x₀, y₀) is the center, it is for example the location of an AZN point. (s_x, s_y) is the spread. In our case, we will use a symmetric spread, so s_x = s_y. The spread parameter represents the size of the influence area of the Gaussian curve.

Let's implement that in C#:

private void ApplyGaussian(double[,] rates, double intensity,
    Point center, double spread)
{
    for (int x = 0; x < 200; x++)
        for (int y = 0; y < 200; y++)
        {
            double xTerm = Math.Pow((x - center.X) / spread , 2.0);
            double yTerm = Math.Pow((y - center.Y) / spread , 2.0);
            rates[x, y] += intensity * Math.Exp(-(xTerm + yTerm));
        }
} 

This function is not optimized at all... but I let you optimize it.

Applying Gaussians

It's time to fill our rates array. It's quite simple:

private void GiveRates(double[,] rates)
{
    foreach (Entity entity in Tissue.Entities)
        ApplyGaussian(rates, 1.0, new Point(entity.X, entity.Y), 50.0);
} 

Varying Parameters

You have to find the best spread. And remember that you can vary spread and intensity according to the entity type (AZN, Hoshimi point, navigation objective). If you choose a small spread parameter, your injection point will be near from an entity. For example, with 5.0, you get on A1:

The injection point is in an area where there are many Hoshimi points.

With 50.0, you get:

With a big spread parameter, this method behaves more like the barycenter method (1^st part of this article).

A Variation of this Algorithm

If you are a good observer, you will notice that xTerm + yTerm is the Euclidian distance divided by the squared spread factor. What happens if we use the Manhattan distance function instead of Euclidian distance? Let's try:

private void ApplyGaussian(double[,] rates, double intensity,
    Point center, double spread)
{
    for (int x = 0; x < 200; x++)
        for (int y = 0; y < 200; y++)
        {
            double power = (double)Utils.ManhattanDistance(center,
                new Point(x, y)) / (spread * spread);
            rates[x, y] += intensity * Math.Exp(-power);
        }
}  

By using this distance function, you will get different results. You have to find which one you prefer. On A1, with the spread factor set to 50, you get:

Final Considerations

With the barycenter method, if you play in a map with only 4 Hoshimi points: one Hoshimi point at each corner of the map, you will be injected exactly in the middle of the map, so you will be very far from each Hoshimi point. By using this Gaussian method, you will ensure to be injected close to an entity (less or more close, depending to your spread factor).

One nice feature of this method is that you can apply a Gaussian with negative intensity over the Pierre's injection point. It will prevent you from injecting near him.

Remember to avoid being injected in bones, because they are not taken into consideration by this algorithm.

Good luck. ;-)

History

This article was published on March 12^th, 2007.

Original article

This article was first published on the official site of Project Hoshimi at http://www.project-hoshimi.com/article.aspx?ID=EN/Raptor/ip2.