🎉 Celebrating 25 Years of GameDev.net! 🎉
Not many can claim 25 years on the Internet! Join us in celebrating this milestone. Learn more about our history, and thank you for being a part of our community!
Your A* results
January 27, 2003 01:34 PM
What are your A* best results? I''ve been working on a A*search
and the best results I can have are solving a random problem which solution was length 12. I had 5 possible operations and it was solved in some seconds. Is it a good result?
This A* I''m working is optimal and complete.
--------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
--------------------------Rory Gallagher and Chico Science music !!!!!!!---------------------------____||~~~~|/TT
1,412
January 27, 2003 01:40 PM
What do you mean length 12? 12 nodes from original position to destination?
What do you mean "5 Operations"?
I've used A* in a small demo program before that searched probably 200 nodes for a path of length 15-20 in nearly an instant. It was a simple ogl program that let you draw lines on a grid and any square with any part of a line in it was considered blocked and wasn't connected to other nodes. If a line went between two squares, both squares would be connected to the others but not to eachother.
The majority of the time was spent in the function that figured out which squares should be connected and which squares had lines in them etc. Originally it recalculated the links each time the path was calculated but when I realized it was the slowest part I made it only recalculate the path after new lines were added.
[edited by - Extrarius on January 27, 2003 2:44:02 PM]
What do you mean "5 Operations"?
I've used A* in a small demo program before that searched probably 200 nodes for a path of length 15-20 in nearly an instant. It was a simple ogl program that let you draw lines on a grid and any square with any part of a line in it was considered blocked and wasn't connected to other nodes. If a line went between two squares, both squares would be connected to the others but not to eachother.
The majority of the time was spent in the function that figured out which squares should be connected and which squares had lines in them etc. Originally it recalculated the links each time the path was calculated but when I realized it was the slowest part I made it only recalculate the path after new lines were added.
[edited by - Extrarius on January 27, 2003 2:44:02 PM]
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
January 27, 2003 01:51 PM
quote: What do you mean length 12? 12 nodes from original position to destination?
Yes, 12 nodes from original position to destination.
quote: What do you mean "5 Operations"?
I have 5 operations that I can do. Go forward, turn left, turn right, pull a box, push a box.
There are boxes with randomic distribuition and I have to do this 5 operantions to find the goal.
well, I think I''m not too far from my objectives, I will continue working. I coded all the program by myself, so I have a lot of optimizations to do....
--------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
--------------------------Rory Gallagher and Chico Science music !!!!!!!---------------------------____||~~~~|/TT
1,412
January 27, 2003 01:58 PM
I can see why your implementation takes so long to execute - my demo was really simple and didn''t have any constraints like yours. Solving such a puzzle game isnt nearly as easy as just finding a path.
"Walk not the trodden path, for it has borne it's burden." -John, Flying Monk
January 27, 2003 02:07 PM
Yes. But I''m very happy with the results until now, A* is very cool.
I made it with a tree, and linked list of pointers for the leaf nodes.
--------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
I made it with a tree, and linked list of pointers for the leaf nodes.
--------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
--------------------------Rory Gallagher and Chico Science music !!!!!!!---------------------------____||~~~~|/TT
122
January 27, 2003 03:49 PM
well, you cannot compare this that easily :
e.g. I have a graph with ~250 nodes, and I want to calculate paths from node1 to node1, node1 to node2, .... node1 to node250, node2 to node1, ... so from each node to each node, the average runtime of searching one path is 340 us, so calculating all paths is about 19-20 seconds on my Celeron466 ... but of course this also depends on the complexity of the graph and so on
e.g. I have a graph with ~250 nodes, and I want to calculate paths from node1 to node1, node1 to node2, .... node1 to node250, node2 to node1, ... so from each node to each node, the average runtime of searching one path is 340 us, so calculating all paths is about 19-20 seconds on my Celeron466 ... but of course this also depends on the complexity of the graph and so on
463
January 27, 2003 05:02 PM
as31415rin: If you want to calculate all the paths then use a more efficient algorithm like Floyd''s All-Pairs.
ai-junkie.com
ai-junkie.com
My Website: ai-junkie.com | My Books: 'Programming Game AI by Example' & 'AI Techniques for Game Programming'
864
January 27, 2003 05:59 PM
...or Dijkstra''s.
manuelb: It isn''t practical or sensible to compare your implementation of A* on your problem to someone else''s implementation of A* on a different problem. You''re comparing apples and oranges. If it works on your problem, then great. If you can optimise your code so that it runs faster... then even better. The ultimate test of your code is the playability of the game. If it runs too slow to make the game enjoyable, THEN you need to improve it, or choose a different algorithm.
Cheers,
Timkin
manuelb: It isn''t practical or sensible to compare your implementation of A* on your problem to someone else''s implementation of A* on a different problem. You''re comparing apples and oranges. If it works on your problem, then great. If you can optimise your code so that it runs faster... then even better. The ultimate test of your code is the playability of the game. If it runs too slow to make the game enjoyable, THEN you need to improve it, or choose a different algorithm.
Cheers,
Timkin
January 28, 2003 04:08 AM
Yes Timkin. But I was only trying to know if my apple is round like an orange 
. I posted it only to have some idea of A* results.
--------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
[edited by - manuelb on January 28, 2003 5:11:55 AM]
. I posted it only to have some idea of A* results. --------------------------
Rory Gallagher blues will never die.
---------------------------
Que que foi, que que foi, O que eh que hah?
[edited by - manuelb on January 28, 2003 5:11:55 AM]
--------------------------Rory Gallagher and Chico Science music !!!!!!!---------------------------____||~~~~|/TT
122
January 28, 2003 05:55 AM
quote: Original post by fup
as31415rin: If you want to calculate all the paths then use a more efficient algorithm like Floyd''s All-Pairs.
ai-junkie.com
well, I know it and I used it some time ago ... but it''s been to static.
this calculation time for all paths is just from a little benchmark program I used when I was optimizing the A* code
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement