Jump to content
• Advertisement

# WOW, I have REALLY optimized A*

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

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

#### Share this post

##### Share on other sites
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

##### Share on other sites
6 seconds ?? depends on what you run it on.

#### Share this post

##### Share on other sites
"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

##### 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

##### 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

##### 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

##### Share on other sites
Zefrieg,
perhaps this could be usefull http://www.cs.ualberta.ca/~nathanst/pathfinding.html

#### Share this post

##### Share on other sites
Quote:
 Original post by KylotanSo, 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

##### 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

##### Share on other sites

• Advertisement
• ### Game Developer Survey

We are looking for qualified game developers to participate in a 10-minute online survey. Qualified participants will be offered a \$15 incentive for your time and insights. Click here to start!

• Advertisement

• ### Popular Now

• 11
• 10
• 9
• 15
• 22
• 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!