Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Newcomers DBPro Corner / a question of A* performance

Author
Message
Olympic
20
Years of Service
User Offline
Joined: 18th Aug 2004
Location:
Posted: 4th Sep 2004 07:26 Edited at: 4th Sep 2004 10:01
Link
I implemented A* by DBc which based on waypoints system
so finally there are about 30 nodes(waypoints) in the map.

The A* function only cost 0.365ms to find a path
I am searching articles to find the tendency that with the number of searched nodes increasing how much the time consumption will be increased?

say 30 searched nodes(waypoints) will take 0.365ms, how about 300 searched nodes? and How many nodes(waypoints) are normally placed in a real game? (like quake?)

Is there any articles talk about the relation between time consumption and the number of searched nodes in search algorithm?

Thanks a lot!
Back to top
Profile PM
Phaelax
DBPro Master
21
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 4th Sep 2004 11:14
Link
The time is going to depend a lot more on how much of your map contains obstacles. A completely empty map will find a path immediately. See where I'm going with this?
Because of the obstacle variable, it's probably why I couldn't find a time function showing how long it takes to find a path.

"eureka" - Archimedes
Back to top
Profile PM Email Website
Arkheii
21
Years of Service
User Offline
Joined: 15th Jun 2003
Location: QC, Philippines
Posted: 4th Sep 2004 11:40 Edited at: 4th Sep 2004 11:44
Link
Quake is fast because it only does a path search every tenth of a second.

Quote: "The A* function only cost 0.365ms to find a path"


Too slow, that's a third of a second! Unless it is intended for something with less intense gameplay, that will affect your framerate.

http://www.aiguru.com/pathfinding.htm

Take a look at the two-tiered pathfinding article.

Back to top
Profile PM
eat much pie
20
Years of Service
User Offline
Joined: 9th Apr 2004
Location: Within the mind of a lowly mortal...
Posted: 4th Sep 2004 23:00
Link
I'm making a checkpoint routing program for this exact problem. It has quite a bit more functionality than A* and is very easy to use. See my website for more info and a beta demo:

http://eatmuchpie.dbspot.com


[href]Checkpoint Router[/href]: My AI Routing Program
Sam Wright
Back to top
Profile PM Email Website
Mentor
22
Years of Service
User Offline
Joined: 27th Aug 2002
Location: United Kingdom
Posted: 5th Sep 2004 04:15
Link
too slow?, he might mean one third of a millisecond, that wouldn`t be too bad and probably explains why he said only, even my "big dumb pathfinder" could do a four hundred nodes in under 1m/sec back when the fastest machine I had was 1.2ghz.

Mentor.

PC1: P4 3ghz, 1gig mem, 2x160gig hd`s, Radeon 9800pro w cooler (3rd gfx card), 6 way speakers.
PC2: AMD 2ghz, 512mb ram, FX5200 ultra, 16 bit SB.
Mini ATX cases suck.
Back to top
Profile PM
Arkheii
21
Years of Service
User Offline
Joined: 15th Jun 2003
Location: QC, Philippines
Posted: 5th Sep 2004 22:24
Link
Oh. I thought it was 1/3 of a second. My mistake.

Back to top
Profile PM
Back to top

Login to post a reply

Server time is: 2024-11-27 08:48:25
Your offset time is: 2024-11-27 08:48:25