Jump to content
  • Advertisement
Sign in to follow this  
Zefrieg

WOW, I have REALLY optimized A*

This topic is 5017 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

Advertisement
If anyone wants the full source of some of the AI stuff I am doing, then just send me an email. It would help to have some people test it out.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
6 seconds ?? depends on what you run it on.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
"but with random search spaces of a million nodes and over a million connections"


how much "over a million conections" ???


network complexity - average number of connections per node


the higher the complexity the longer it will take to find a path


example a 2D cartesian map grid has 4-way or 8-way complexity
(1000x1000 grid - 1 million nodes and upto 4/8 million connections)

Share this post


Link to post
Share on other sites
Actually, I had that on debug, and had some things running in the background. Also, my cost function includes the sqrt() function and two multiplies, and the start to goal nodes are usually are far apart. Here are some tests on different numbers of nodes

10,000 nodes = 20 ms
100,000 nodes = 100 ms
1,000,000 nodes = 2342 ms

Seems like it grows in time complexity by O(n). There is only one O(log n) function in the main loop, and both a O(log n) and O(1) functions in the inner loop.

Share this post


Link to post
Share on other sites
There are at least two per node, and there are on average an extra two per node. So I guess that would be 4.

The 1,000,000 test had 4,000,000 connections.

It isn't done in a 2d grid. Instead it goes more like this


............-------------------
.........../
.....------
.../
./oooo
|oooooo
.\oooo
........------
...........\-------------------



o - random x,y coordinate of start
goal is somewhere on the outer edge of the opposite side.

Anyway, I haven't done any realistic tests. I will try to test against other methods. Any idea what the best way to set up the search space would be?

Share this post


Link to post
Share on other sites
So, is all you're saying that you're using a more efficient structure than a linked list for storing nodes?

Share this post


Link to post
Share on other sites
Quote:
Original post by Kylotan
So, is all you're saying that you're using a more efficient structure than a linked list for storing nodes?


Well, I eliminated the need for searching through an open and closed list of nodes.

Share this post


Link to post
Share on other sites
Hi.

First, are the paths optimal? If not, how unoptimal are we talking about here?
Second, what is the size of the grid you're testing on? 1000x1000?
Finally, have you checked the results with another algorithm, a stable, and easy to debug one?

I find those results EXTREMELY difficult to belive!!!

Thanks.

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.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!