Java-Gaming.org    
Featured games (91)
games approved by the League of Dukes
Games in Showcase (578)
games submitted by our members
Games in WIP (498)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  How fast should A* run?  (Read 4500 times)
0 Members and 1 Guest are viewing this topic.
Offline appel

JGO Wizard


Medals: 49
Projects: 5


I always win!


« Posted 2007-03-02 05:24:57 »

I'm wondering, I have a grid of 50x50... and A* takes about 1.4 ms going from bottom left to top right, and there are no obstacles.
My implementation is using diagonal heuristics and PriorityQueue for both open and closed lists, although using a LinkedList for closed set doesn't matter much.

I have tried AIJ (https://aij.dev.java.net/) ... and it runs 0.8 ms (same setup, 50x50 grid and going from bottom-left to top-right). Although the first few attempts run anywhere between 1-8 ms, but after those it constantly runs at under 0.8 ms.

Clearly, mine is taking nearly twice as long, just wondering what could be the problem Smiley

(Of course this is also relative to the computer being run on.)

Any general ideas? If anyone that knows A* in and out is interested in checking out my code, please let me know... I'll PM you a link.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline SluX

Junior Member





« Reply #1 - Posted 2007-03-02 11:49:40 »

i remember that ve used min heap for implementation....tho it was long time ago...must do a refresher course Smiley

"Intelligence is the most beautiful gift and the greatest temptation which one life can receive from the gods."Me Cheesy
Play strategic football
Offline Eliwood

Junior Member




Stencyl


« Reply #2 - Posted 2007-03-13 07:25:47 »

What does does your graph/map look like? If there are lots of walls and obstacles, then using the current heuristic may not be the best choice and using something like a cluster heuristic would better suit that. What does your fill pattern look like currently?

Alternatively, you could look at a different data structure, but if switching to a linked list has no effect, then switching to something better will also have little effect since that doesn't appear to be the bottleneck. I would say though that priority queue isn't optimal. You might want to try a heap as the poster above suggests or a bucketed priority queue instead.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline appel

JGO Wizard


Medals: 49
Projects: 5


I always win!


« Reply #3 - Posted 2007-03-16 01:43:09 »

I've read amits a* page, it has nice info on heuristics for A*. Are there any other sources, different types of heuristics that I should explore?

I'm googling for the "cluster heuristic" now...don't seem to find any source explaining it.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline g666

Junior Member





« Reply #4 - Posted 2007-03-16 16:00:44 »

You are still getting that time? Your demo is many times faster, if you remember to warm it up a few times first.

desperately seeking sanity
Offline appel

JGO Wizard


Medals: 49
Projects: 5


I always win!


« Reply #5 - Posted 2007-03-16 18:00:34 »

Yes, I managed to speed it up a lot Smiley I'm happy with the speed now.

I'm wondering about heuristics, I currently have 5 heuristics:

- Manhattan
- Euclidean
- Diagonal
- Diagonal with tie-breaker
- Diagonal with tie-breaker cross-product

But I'm interested in other heuristics, but they are hard to find.

Check out the 4K competition @ www.java4k.com
Check out GAMADU (my own site) @ http://gamadu.com/
Offline g666

Junior Member





« Reply #6 - Posted 2007-03-16 21:19:50 »

i read somwhere about a mipmaped one, where the mipmaps are based upon the passibilty of the more refined level.

desperately seeking sanity
Offline ravenger

Senior Newbie





« Reply #7 - Posted 2007-04-04 16:50:12 »

Yes, I managed to speed it up a lot Smiley I'm happy with the speed now.

I'm wondering about heuristics, I currently have 5 heuristics:

- Manhattan
- Euclidean
- Diagonal
- Diagonal with tie-breaker
- Diagonal with tie-breaker cross-product

But I'm interested in other heuristics, but they are hard to find.
I guess heuristics are largely dependent on what kind of search space you have. I can imagine that some heuristics fit squarebased searchspaces more, while others fit for example hexagonal searchspaces more.
Offline JAW

Junior Member





« Reply #8 - Posted 2007-04-25 17:01:40 »

There are some articles about A* optimisation in Game Programming Gems or AI Programming Books.

Some use tricky sorting algorithms to the open or closed list to optimize. I dont have the details in mind.

-JAW
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (26 views)
2014-04-15 18:08:23

BurntPizza (21 views)
2014-04-15 03:46:01

UprightPath (37 views)
2014-04-14 17:39:50

UprightPath (19 views)
2014-04-14 17:35:47

Porlus (35 views)
2014-04-14 15:48:38

tom_mai78101 (61 views)
2014-04-10 04:04:31

BurntPizza (119 views)
2014-04-08 23:06:04

tom_mai78101 (219 views)
2014-04-05 13:34:39

trollwarrior1 (186 views)
2014-04-04 12:06:45

CJLetsGame (193 views)
2014-04-01 02:16:10
List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:05:20
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!