Estimating Distances in Project Hoshimi

• Download source - 499 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.

What are Distance Functions for?

Moving your bots is the task that takes most of the time in a Project Hoshimi game. In this article, I will explain some ways to calculate approximations of a distance between 2 points, then I will give you some tricks to handle distances easily.

Distance Functions

A path from a point to another takes a certain amount of turns. You can know this number of turns if you develop your own pathfinding, but doing such a calculation is a time costly operation.

There are calculations that can help you to know how far a point is from you. There are mainly 2 ways to estimate the distance between 2 points:

Euclidian Distance

It is the distance that you would see if you trace a straight line between the two points. You can easily calculate it with:

public static int EuclidianDistance(Point ptA, Point ptB)
{
    return Math.Sqrt((ptA.X - ptB.X) * (ptA.X - ptB.X)
        + (ptA.Y - ptB.Y) * (ptA.Y - ptB.Y));
}

Take a look to this picture. The Euclidian distance from the red cell to other ones is shown:

This is the distance that the GameEngine uses to know if you are close enough to attack a bot. This is also the distance used to know if a bot can see an enemy bot near to him. The game engine uses a strict comparison. For example, if you are in the red call, and you have set the DefenseDistance to 4, the area you can attack is the green one:

Manhattan Distance

But there are cases where Euclidian distance will not give you good information. For example, if you want to get an estimation of the distance to walk for a bot between two points. NanoBots can only walk vertically and horizontally. So you cannot use Euclidian distance to get an accurate information to know the time your bots will need to walk from a point to another one.

The Manhattan distance gives you a better information. You must use the following expression to calculate it:

public static int ManhattanDistance(Point p1, Point p2)
{
    return Math.Abs(p1.X - p2.X) + Math.Abs(p1.Y - p2.Y);
}

The Euclidian distance from the red cell to the other ones is drawn there:

You can notice that if there is no obstacle, the Manhattan distance is exactly the distance your bot will walk. Look at this picture :

Whatever path the bot will take, the distance will ever be the same: 11 steps horizontally + 7 steps vertically. So the distance will ever be 18.

To know approximately the number of turns the bot will be moving, you should use a multiplying factor, because depending on the density of the tissue, and the streams, the speed on a cell will vary. For example, on low density, the bot will make 1 step every 2 turns. But if there is a stream, it can take 4 turns instead of 2. So you should multiply the Manhattan distance by at least 2 (bots rarely walk faster, except NanoExplorers).

Real Distance

If there is an obstacle on the path of the bot, calculating the Manhattan distance will not give you the real distance. To get a more accurate value, you need to implement a pathfinder. But remember that using a pathfinder is very time consuming. Your WhatToDoNextEvent function has to return within 200 milliseconds, so you can only make few calculations with a pathfinder.

Speed of Nano Bots

Your bots will not move at the same speed depending on the cell it stands in. Here is a quick help about the speed of bots.

The NanoExplorer moves at the same speed everywhere: it walks 1 cell in 1 turn. All other bots (that can move) make 1 step in an entire number of turns. Blood density and streams affects this number. Bots can move up, down, left or right. They cannot move diagonally in one step. A bot is not oriented, there is no need to turn when you move in one direction, then in one other. They can seem oriented in viewers but it is only esthetical.

Blood Densities

There are 3 levels of blood density:

• Low density

Low density are red cells in the 2D Viewer. Bots take 2 turns to do a step in low density.

• Medium density

Medium density are blue cells in the 2D Viewer. Bots take 3 turns to do a step in medium density.

• High density

High density are green cells in the 2D Viewer. Bots take 4 turns to do a step in high density.

You can retrieve tissue density like this:

switch (tissue[x, y].AreaType)
{
    case AreaEnum.LowDensity:
        // Some code
        break;
    case AreaEnum.MediumDensity:
        // Some code
        break;
    case AreaEnum.HighDensity:
        // Some code
        break;
    default:
        // Some code
        break;
}

Streams

Streams are regions of the tissue where direction in which you move modifies the speed of your bot. Streams are oriented in a direction.

• If you move in the opposite direction of the steam, it takes 2 more turns to do a step.
• If you move in any other direction, it takes 2 less turns to do a step. But if the calculated turns should be 0, it is increased to 1.

For example, if you move perpendicularly of a stream in a low density blood, you take 1 turn to do 1 step (2 - 2 = 0, so it is increased to 1).

You can retrieve the direction of the stream at a given point by using the following code, for example:

public BloodStreamDirection? GetStream(Point pt)
{
    foreach (BloodStream bs in this.Tissue.BloodStreams)
    {
        if (bs.Rectangle.Contains(pt))
            return bs.Direction;
    }
    return null;
}

NanoBlockers

Enemy NanoBlockers will slow your bots. NanoBlockers have a radius defined in Utils.BlockerLength. To know if you are in the radius of an enemy bot, you should use Euclidian distance. If one of your bots is in the radius of an enemy NanoBlocker, it will remain in the cell 6 more turns (the value is stored in Utils.BlockerStrength).

Points of Interest

Data contained in this article should be quite useful if you plan to develop your own pathfinder.

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/distances.