Platinium Rift : Technical question

#1

I’m a software developer and i tried the platiniun challenge. that was good, i discover many things and algo that i never use. As the challenge is finished i have a question about the Djisktra algorythm.

I used that algorytm when I need to move a pod wich is located deep in my territory to a target on the frontline. But the problem is that it’s really slow (I means givig the 100ms we have). Example : I have al africa, europe, asia, and only miss one territory in south asia island.

But i saw many IA that could move all theirs pod to a target, how did you manage that?

Creating zones? Using a previous calculate path? Random?

#2

anti-object aproach. I give each of my zone a “scent” that fade away with distance. So pods follow the strongest scent and reunite :slight_smile:

After, that up to you to define what is more “scentful” than the rest

#3

Hum, that a really interesting approach.
Moreover it’s easy and fast to implement.

But with the scent approach, how will you do if a pod is too far to smell any scent?

I have the same problem when it’s come to decide witch target to aim.

#4

You can pre-calculate on turn 1 the distance matrix.

You initialise the matrix with hudge distances :
distances[i][j] =
| 800 if i != j
| 0 if i == j

Then for each cell, you try to see if you can go faster to your destination by first going to one of its neighbour and then to the destination.

Its gives you something like this:
for i in (0, zoneCount -1):
---- for j in (0, zoneCount -1):
--------- for k in (neighbours(i)):
--------------- distances[i][j] = min(distances[i][j], distances[k][j] + 1)

You iterate this part as long as the distance matrix changes when you do.

Once this is over, you have all the distances precomputed and distances[i][j] == 800 means i and j are on different continents.

Now say you want to find the next step in going from the cell c to te cell dest. You can do this:

for k in neighbours©:
------ if distances[k][dest] < distances[c][dest]
-------------return k

Hope it’s clear enough.

#5

Dijkstra’s algorithm is actually really fast considering the low numbers of nodes and vertices. I computed every shortest path once at start and my first turn was taking less than 60ms in PHP without optimization (that includes reading input, computing every shortest paths but also various others things) before.map change (thus with a giant continent) and less than 50ms after.

Note that you don’t really need to follow Dijkstra’s algorithm but simply do a breadth-first-search with a simple queue as every distances between neighbours are the same.

#6

I used a simple system to reduce the number of operations : first I divided the map in continents.
For each continents, if I have no pods and no zone at me and no neutral zone anymore, OR if all zones are mine, then the continent is “out”.

therefore I don’t calculate anything for it, it’s just “out of the game”.

for continents remaining, I calculate path for a zone only if i have pods on it.

with Java, i didn’t time out.

#7

You put a big scent on the case that matter, then -1 per case distance.
A basic implementation that i use was:

  • every case that doesn’t belong to me is interesting
  • case with much platinum is even more interesting
  • when you have to choose between two equal scent, go to the one with the less pods on it.

It did a really offensive strategy, but a really bad defensive one, since i left my lands unprotected. I didn’t have the time to play more platinum rift, but i think i would have buffed up this implementation. The keys is to define your priorities.

#8

@CvxFous :
Ok thanks for that really good idea, I will do some tests and try it very soon.
Yeah the balance between offence and defense is really hard to find. I guess the best way is to have an IA that couls adapt to the situation and being defensive or agresive.
Man I love AI, I should have start doing it long ago, why did I just start last month? :smiley:

#9

Ok guys thanks for all,

You gave me some good ideas, precaculate the distance with a breadth-first searh is brilliant.

I also calculate the shortest path only on some eligible territories (with pod and no ennemy within a distance of 2).
But not storing it (That a way of improvement)

And I guess my implementation of Dijktrat is really slow. I’ll try to find the bottleneck.

Thanks for all your reply

#10

I used the same algorithm than Stan.
For information, this algorithm is called “Floyd-warshall”.
You can have more informations about it here: http://en.wikipedia.org/wiki/Floyd-Warshall_algorithm

#11

Cerobe, you must be aware that Djisktra is suited for weighted graph. It helps you to find the path which has the smallest cost but in Rift contest, this is a un-weighted graph (every vertex costs 1). So a breath-first search is enough. Furthermore, for performance purpose you should separate the disconnected graphs.

I used scala and had no performance issue at all.

#12

I used a weigth of one for each vertex.

I kind of use the breath-first algo in other point of my AI, without knowing it. And without thinking that i could use it to find the shortest path. I guess my lack of experience with AI and games algo shows here.

I also didn’t know about the Floyd–Warshall algorithm, i’ll defenitely use it next time for game initialisation.