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?
You can pre-calculate on turn 1 the distance matrix.
You initialise the matrix with hudge distances :
| 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:
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.
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.
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.
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?
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 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.