WOW, I have REALLY optimized A*
Author
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.
"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)
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)
Author
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.
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.
Author
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
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?
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?
So, is all you're saying that you're using a more efficient structure than a linked list for storing nodes?
Author
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
