[FreecivDev] Priority queue for Dijkstra
[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
I am now hacking at the air routefinding functions, trying to adapt it to
AI needs. As a blueprint of a "good" implementation I am using Raimar's
goto_agent code which uses a list and a hash table to hold reachable
tiles for Dijkstra algorithm.
The list is sorted from time to time to find the next nearest tile.
This aroused my suspicions, since we really need a priority queue and the
naive implementation of a priority queue is just a list with a
find_maximum_element function  an O(n) algorithm. Being a poorly
educated peasant boy, I didn't know how fast is qsort, but I went to the
big town and found a nice set of lecture notes:
http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/index.html
where I am told that qsort is O(n log(n)), with a potentially large
constant factor (plus genlist stuff on top of that).
The current implementation of priority queue in gotohand.c is actually
O(1)  as far as I can tell  due to the limited set of possible
priorities. But it's a bit ugly. Maybe there is a standard heap method
( heap is O(log(n)) ) somewhere in C or hidden in freeciv code?
The list of priorities for planes can be bounded by map.xsize + map.ysize
but with some potential problems. If SINGLE_MOVE ever goes up from 3
thought, the maximum priority for land move will increase too, so heap
might be a good idea.
Best wishes,
G.
P.S. Oh ye, computer scientists, please spare me from the wrath of you
flamethrowers if I erred in the above message.
 [FreecivDev] Priority queue for Dijkstra,
Gregory Berkolaiko <=
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Gregory Berkolaiko, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Jason Short, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16
 [FreecivDev] Re: Priority queue for Dijkstra, Raimar Falke, 2002/03/16

