[web] A* performance issue (mysql and php)

I have never, ever even considered the possibility that someone might write A* in pure SQL. Well done!

But if you want it to perform you'll need to write it in something else. There is a lot of overhead to SQL queries. For fetching data this isn't as big of a deal, because compared to IO latency it is negligible, but for A* it's a killer. Plus you'll have more flexibility to optimize with a general purpose language over SQL.

Big performance issue of php is to get the cheapest from the open list.

How are you storing your open list? Are you recalculating the cost of each node in the open list every time you are fetching an item from it? How are you keeping your closed list?

For mysql the IO can't be the problem because I use MEMORY tables.

I have done the php version a while before and didn't saved it :-(
But as far as I remember I just had an array with the map as hash and the open/closed list was a simple one with just sector-id.
for($i=1;$i<count($openList);$i++)
if($map[$openList[$i]]["cost"] < $cheapest)
{ $cheapest = $map[$openList[$i]]["cost"]; $cheapestID = $openList[$i]; }

For mysql the IO can't be the problem because I use MEMORY tables.

I have done the php version a while before and didn't saved it :-(
But as far as I remember I just had an array with the map as hash and the open/closed list was a simple one with just sector-id.
for($i=1;$i<count($openList);$i++)
if($map[$openList[$i]]["cost"] < $cheapest)
{ $cheapest = $map[$openList[$i]]["cost"]; $cheapestID = $openList[$i]; }

I wasn't saying that IO was your problem, I was just saying that there is more overhead to SQL queries, which usually doesn't matter because IO time overshadows the statement overhead. You're using memory tables, which eliminates IO latency, but I doubt selecting from a memory table is as fast as taking an item off the end of a priority queue, or reading/settings boolean flags on an array, which what you could be doing in PHP.

for($i=1;$i<count($openList);$i++)
if($map[$openList[$i]]["cost"] < $cheapest)
{ $cheapest = $map[$openList[$i]]["cost"]; $cheapestID = $openList[$i]; }

You could probably improve the performance of this significantly by making a small change. Use whatever built-in function there is in php to sort your open list by cost. Whenever you push an item into the open list, sort it afterward. The built-in php sort will probably be implemented at low level, so it should be faster than anything you could write yourself in php. With a sorted open list, pulling items off the open list will not require iteration over the entire list. You can just take the first item off the top. An even better solution would be to use a priority queue, which would maintain a sorted open list for you.

Also, you're using an associative array as the individual nodes in your open list. Accessing the cost in your nodes is likely very expensive. Using a property on a user defined type would be more efficient (if you can do that sort of thing in php. I don't know php.)

The normal sort of php isn't faster but I found a SplMinHeap Class in php, this looks very interesting! Thanks for the hint.