Eh [Edited by - Zefrieg on September 22, 2004 10:46:48 PM]

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.

6 seconds ?? depends on what you run it on.

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

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.

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?

So, is all you're saying that you're using a more efficient structure than a linked list for storing nodes?

Zefrieg,
perhaps this could be usefull http://www.cs.ualberta.ca/~nathanst/pathfinding.html

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.