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
Injection point is a very important part of your strategy. Finding a good injection point can make you the winner. You can also lose a game against an inferior player just because you have chosen a bad injection point. There are several ways to find an injection point. Some are better than others. I will explain some ways to find an injection point.
In this article, I will explain a very simple method to find an injection point.
Let's Start
First thing to know: you can spend as much time as you want to find your injection point. For example, if your program needs 5 seconds to find your injection point, you will lose 25 turns. But in my opinion, it is better to lose some turns at the beginning of the game, and find a good injection point.
The method I will explain is the one used in the intermediate mode:
This method has 2 steps:
- First, it calculates the "best" point to inject in the map ("best" depends on the method used). I will give you details about this calculation later.
- Then, it finds the nearest Hoshimi Point from this point. It also works with the nearest AZN Point, or the nearest Objective Point.
It can be interesting in being injected on a Hoshimi Point, because you can immediately build a NanoNeedle. This is why the second step can be useful.
Finding the Better Point
First, you have to find the "best" point in the map. The more difficult thing when finding an injection point in Project Hoshimi, is to define what you call "best". This first step is the most important in this method but there are many different solutions to calculate this point.
The intermediate mode engine uses a very simple method to find such points. I am going to explain this method. But there are many other methods that can give other "best" points (I will explain another method in the next article).
First the engine calculates the barycenter of all the Hoshimi Points, then the barycenter of all the AZN Points, then the barycenter of all the Objectives Points.
Now, the engine has 3 points. To find the "best" point in the map, it computes the barycenter of these 3 points, using for each of them the weight indicated in your strategy.
In this example, the weight given to Hoshimi Points is 5, 2 to AZN Points, and 1 to Objectives Points.
So the first thing to do is to find the barycenter of the Hoshimi Points:
public Point HoshimiPointBarycenter()
{
Point sum = Point.Empty;
int hoshimiPointsCount = 0;
foreach (Entity entity in Tissue.Entities)
{
if (entity.EntityType == EntityEnum.HoshimiPoint)
{
Point hoshimiPointLocation = new Point(entity.X, entity.Y);
sum += (Size)hoshimiPointLocation;
hoshimiPointsCount++;
}
}
Point result = new Point((int)Math.Floor((double)sum.X
/ (double)hoshimiPointsCount),
(int)Math.Floor((double)sum.Y
/ (double)hoshimiPointsCount));
return result;
}
You can easily adapt this to the AZN Points and to the Objectives Points.
Now, it's quite easy. First, let's define some constants :
private const float HoshimiPointsWeight = 5;
private const float AZNPointsWeight = 2;
private const float ObjectivesPointsWeight = 1;
You may have noticed that I have chosen the same values that are in the intermediate mode screenshot. These constants will help you to tune your program. You have to do several tests to find the best values. You can also compute dynamically these values according to the map. The intermediate mode doesn't allow you to do that.
Finally, you have compute the final barycenter, using the defined weights constants:
public Point FindInjectionPoint()
{
Point hoshimiBarycenter = HoshimiPointBarycenter();
Point aznBarycenter = AznPointBarycenter();
Point objectivesBarycenter = ObjectivesPointBarycenter();
return new Point((int)Math.Round(
((HoshimiPointsWeight * hoshimiBarycenter.X)
+ (AZNPointsWeight * aznBarycenter.X)
+ (ObjectivesPointsWeight * objectivesBarycenter.X)) /
(HoshimiPointsWeight + AZNPointsWeight + ObjectivesPointsWeight)),
(int)Math.Round(
((HoshimiPointsWeight * hoshimiBarycenter.Y)
+ (AZNPointsWeight * aznBarycenter.Y)
+ (ObjectivesPointsWeight * objectivesBarycenter.Y)) /
(HoshimiPointsWeight + AZNPointsWeight + ObjectivesPointsWeight)));
}
For the map A1, you will get this injection point (location of the NanoAI) with the parameters HoshimiPointsWeight = 5, AZNPointsWeight = 2, ObjectivesPointsWeight = 0.
For the map A2, with the same parameters, you will get this injection point (location of the NanoAI):
You can notice that the injection point chosen is often in the middle of the map with this method.
You can try to put 5, 2 and 0 in an intermediate mode strategy, and you will see that the injection points chosen are the same.
Finding the Nearest Hoshimi Point
Now we have a point. But theoretically, this point can be located in a non moveable area (bones), or very far from every important areas (Hoshimi points, AZN points). So, it can be interesting to find the nearest Hoshimi Point (for example) from it. This way, you are sure to be injected near at least one Hoshimi Point (in fact you are injected ON a Hoshimi Point). It is quite easy to do that. Here is the code to find the nearest Hoshimi Point from another point. You can easily adapt it to AZN Point and Objective Point.
public Point FindNearestHoshimiPoint(Point from)
{
Point nearestHoshimiPoint = Point.Empty;
int nearestDistance = int.MaxValue;
foreach (Entity entity in Tissue.Entities)
{
Point entityLocation = new Point(entity.X, entity.Y);
if (entity.EntityType == EntityEnum.HoshimiPoint
&& Utils.Distance(entityLocation, from) < nearestDistance)
{
nearestDistance = Utils.Distance(entityLocation, from);
nearestHoshimiPoint = entityLocation;
}
}
return nearestHoshimiPoint;
}
This step is less important than the first. It is just useful if you want to be sure to start on an Hoshimi Point.
Telling Your NanoAI to Do That
Finally, you have to add these lines in the ChooseInjectionPoint event, in order to choose the calculated injection point:
Point bestPoint = FindInjectionPoint();
this.InjectionPointWanted = FindNearestHoshimiPoint(bestPoint);
Now, test it on some maps.
On A1, if you take the same parameters than above but you choose to be injected on the nearest Hoshimi Point from the calculated point, you will be injected here:
You can notice that the second algorithm will find the nearest Hoshimi Point from the point found by the first algorithm.
Maybe you will have problems with this method on some maps. For example, if you have a map with 4 Hoshimi points in the left of the map and 4 Hoshimi points in the right of the map, the point found (by the first step) will be on the middle of the map, which is far from every Hoshimi point!
Conclusion
In this article, I have explained how to reproduce the Injection Point finder of the intermediate mode. But with the developer mode, you can go much further than that. In the next part of this article, I will show you an algorithm to find a better point for the first step of this method (but more complicated).
History
This article was published on March 12th, 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/ip1.
Submit an article or tip
