<!--------------------------------------------------------------------------->
<!-- INTRODUCTION
The Code Project article submission template (HTML version)
Using this template will help us post your article sooner. To use, just
follow the 3 easy steps below:
1. Fill in the article description details
2. Add links to your images and downloads
3. Include the main article text
That's all there is to it! All formatting will be done by our submission
scripts and style sheets.
-->
<!--------------------------------------------------------------------------->
<!-- IGNORE THIS SECTION -->
<html>
<head>
<title>The Code Project</title>
<Style>
BODY, P, TD { font-family: Verdana, Arial, Helvetica, sans-serif; font-size: 10pt }
H2,H3,H4,H5 { color: #ff9900; font-weight: bold; }
H2 { font-size: 13pt; }
H3 { font-size: 12pt; }
H4 { font-size: 10pt; color: black; }
PRE { BACKGROUND-COLOR: #FBEDBB; FONT-FAMILY: "Courier New", Courier, mono; WHITE-SPACE: pre; }
CODE { COLOR: #990000; FONT-FAMILY: "Courier New", Courier, mono; }
</style>
<link rel="stylesheet" type=text/css href="http://www.codeproject.com/styles/global.css">
</head>
<body bgcolor="#FFFFFF" color=#000000>
<!--------------------------------------------------------------------------->
<!------------------------------- STEP 1 --------------------------->
<!-- Fill in the details (CodeProject will reformat this section for you) -->
<pre>
Title: Estimating distances in Project Hoshimi
Author: Flavien.charlon
Email: flavien.charlon@ecl2007.ec-lyon.fr
Environment: Visual Studio 2005
Keywords: C#, Artificial intelligence, Computation
Level: Beginner"
Description: An article explaining the different distance functions usable in Project Hoshimi.
Section C#
SubSection C# Algorithms
</pre>
<!------------------------------- STEP 2 --------------------------->
<!-- Include download and sample image information. -->
<ul class=download>
<li><a href="hoshimidistances.zip">Download source - XXX Kb</a></li>
</ul>
<p><img src="hoshimidistances.gif" alt="Sample Image - maximum width is 600 pixels" width=600 height=375></p>
<!------------------------------- STEP 3 --------------------------->
<!-- Add the article text. Please use simple formatting (<h2>, <p> etc) -->
<h2>Introduction</h2>
<p>Project Hoshimi is a part of the Imagine Cup challenge. <a href="http://www.imaginecup.com/">Imagine Cup</a> 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".
<h2>What are distance functions for?</h2>
<p>Moving your bots is the task that take 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 easily distances.</p>
<h2>Distance functions</h2>
<p>A path from a point to another take 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.</p>
<p>There are calculations that can help you to know how far a point is from you. There are maily 2 ways to estimate the distance between 2 points:</p>
<h3>Euclidian distance</h3>
<p>It is the distance that you would see if you trace a straight line between the two points. You can easily calculate it with :</p>
<pre lang= cs>
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));
}
</pre>
<p>Take a look to this picture. The euclidian distance from the red cell to other ones is shown :</p>
<p><img src="hoshimidistances1.jpg" width="196" height="183" /></p>
<p>This is the distance that the GameEngine use to know if you are enough close to attack a bot. This is also the distance used to know if a bot can see an ennemy bot near to him. The game engine uses a strict comparison. For exemple, if your are in the red call, and you have set the <code>DefenseDistance</code> to 4, the area you can attack is the green one :</p>
<p><img src="hoshimidistances2.jpg" width="215" height="215" /></p>
<h3>Manhattan distance</h3>
<p>But there are cases where euclidian distance will not give you a good information. For exemple, 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.</p>
<p>The Manhattan distance gives you a better information. You must use the following expression to calculate it:</p>
<pre lang= cs>
public static int ManhattanDistance(Point p1, Point p2)
{
return Math.Abs(p1.X - p2.X) + Math.Abs(p1.Y - p2.Y);
}
</pre>
<p>The euclidian distance from the red cell to other ones is drawn there:</p>
<p><img src="hoshimidistances3.jpg" width="195" height="170" /></p>
<p>You can notice that if there is no obstacle, the manhattan distance is exactly the distance your bot will walk. Look at this picture :</p>
<p><img src="hoshimidistances4.jpg" width="285" height="209" /></p>
<p>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.</p>
<p>To know approximativerly 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 exemple, 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).</p>
<h3>Real distance</h3>
<p>If there is an obstale on the path of the bot, calculating the mahattan 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 consumming. Your WhatToDoNextEvent function has to return within 200 milliseconds, so you can only make few calculations with a pathfinder.</p>
<h2>Speed of nano bots</h2>
<p>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.</p>
<p>The NanoExplorer move at the same speed everywhere: they walk 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.</p>
<p><img src="hoshimidistances5.gif" width="81" height="80" /></p>
<h3>Blood densities</h3>
<p>There are 3 levels of blood density:</p>
<ul>
<li><strong>Low density</strong></li>
</ul>
<p>Low density are red cells in the 2D Viewer. Bots take <strong>2 turns</strong> to do a step in low density.</p>
<ul>
<li><strong>Medium density</strong></li>
</ul>
<p>Medium density are blue cells in the 2D Viewer. Bots take <strong>3 turns</strong> to do a step in medium density.</p>
<ul>
<li><strong>High density</strong></li>
</ul>
<p>High density are green cells in the 2D Viewer. Bots take <strong>4 turns</strong> to do a step in high density.</p>
<p>You can retrieve tissue density like this:</p>
<pre lang= cs>
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;
}
</pre>
<h3>Streams</h3>
<p>Streams are regions of the tissue where direction in which you move modifies the speed of your bot. Streams are oriented in a direction.</p>
<ul>
<li>If you move in the opposite direction of the steam, it takes <strong>2 more turns</strong> to do a step. </li>
<li>If you move in any other direction, it takes <strong>2 less turns</strong> to do a step. But if the calculated of turns should be 0, it is increased to 1.</li>
</ul>
<p>For exemple, 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).</p>
<p>You can retreive the direction of the stream at a given point by using following code, for exemple:</p>
<pre lang= cs>
public BloodStreamDirection? GetStream(Point pt)
{
foreach (BloodStream bs in this.Tissue.BloodStreams)
{
if (bs.Rectangle.Contains(pt))
return bs.Direction;
}
return null;
}
</pre>
<h3>NanoBlockers</h3>
<p>Ennemy NanoBlockers will slow your bots. NanoBlockers have a radius defined in Utils.BlockerLength. To know if you are in the radius of an ennemy bot, you should use Euclidian distance. If one of your bots is in the radius of an ennemy NanoBlocker, it will remain in the cell <strong>6 more turns</strong> (the value is stored in <code>Utils.BlockerStrength</code>).</p>
<h2>Points of Interest</h2>
<p>Datas contained in this article should be quite useful if you plan to develop your own pathfinder.</p>
<p>Good Luck !</p>
<h2>History</h2>
<p>03/12/2007: This article is published</p>
<h2>Original article</h2>
<p>This article was first published on the official site of Project Hoshimi : <a href="http://www.project-hoshimi.com/article.aspx?ID=EN/distances">http://www.project-hoshimi.com/article.aspx?ID=EN/distances</a>.</p>
<!------------------------------- That's it! --------------------------->
</body>
</html>
Submit an article or tip