Jump to content
  • Advertisement
Sign in to follow this  
IndianaX

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

This topic is 2597 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all,

I try to write a A* path finding for a browser game.
It is a 2D 100 x 100 universe where every sector have a 3D 100 x 100 x 100 space and may be connected thru wormholes.

With mysql procedures it takes more than 60 seconds :-(
I also tried it with php but that takes even longer.
Big performance issue of php is to get the cheapest from the open list.
But I have no idea how to analyse mysql procedures.

I attache the mysql version with some example data.
Import & call eu2calc(1); should run it.

C'ya,
Indiana

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites

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?


Share this post


Link to post
Share on other sites
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]; }

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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.)

Share this post


Link to post
Share on other sites
The normal sort of php isn't faster but I found a SplMinHeap Class in php, this looks very interesting! Thanks for the hint.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!