A* V1.0
Displaying 1-20 of 24 total.
12
next
RageCage
|
Click here to download
I heard Toen wanted to use it so I decided to release it somewhat earlier than planned but its here and its working perfectly. The pathfinding generally takes well under a half-second to find its target and start moving on my 1Ghz computer.
If you do end up using this, I suggest you try changing the values in AStar.vh to:
#define H_D 1
#define G_D 0
#define GC_D 0
as you will find it will go MUCH faster but it just wont find as short of a path, and it wont be true A* =p
Please post questions, comments, anything you see that could be better, or any optimizations I could make. Currently it uses binary heaps which is the biggest and most powerful optimization I could find so... I dunno if I can do a whole lot more to optimize it but, whaddya think?
Note: I will be releasing another one soon that will allow you to use larger nodes which will both optimize it heavily and allow you to use entities with larger than 16x16 hotspots. ^_^
Posted on 2004-05-22 22:34:45 (last edited on 2004-05-23 19:11:45)
|
mcgrue
|
You, sir, deserve a trophy.
Posted on 2004-05-22 22:43:13
|
el_desconocido
|
Yes, I give A* an A+. Assuming I ever get of my ass and try and port/update Live Battle, I shall put this to good use.
El
Posted on 2004-05-22 23:03:05
|
mcgrue
|
So, now it's feasable to make a SoM battle system in v3, right Rage? :D
Posted on 2004-05-22 23:07:57
|
RageCage
|
maybe, I'm not familiar with SoM... I'm making a tactics battle system and a click based walking system but if you were to do a realtime battle system like diablo, this would make it much easier ^_^
Posted on 2004-05-22 23:19:29
|
RageCage
|
Speaking of which... If there are any artists out there who would be willing to help with my game, I need people who would be dependable. Anyone good at art can help, and I can guarantee this is a project that won't die.
Posted on 2004-05-23 01:05:29
|
Rysen
|
Totally awesome Rage. Great job!
Posted on 2004-05-23 09:40:37
|
Buckermann
|
Fantastic implementation.
I've seen many commercial games with a much worse pathfinding.
You deserve a hug.
Posted on 2004-05-23 15:14:07
|
RageCage
|
Latest version
ok I added the larger node/chr support, now it is truely finished! thanks for all the comments ^_^
Posted on 2004-05-23 19:07:46
|
andy
|
On an unrelated note, those are almost the worst constant names ever.
The worst being:
#define O 0 // output pipe
#define I 1 // input pipe
Posted on 2004-05-23 20:18:41
|
RageCage
|
lol
Posted on 2004-05-23 20:22:31
|
RageCage
|
hmm just one more note...
to my surprise the default setting for H_D G_D and GC_D makes the path screwy compared to what it should be. I'm not really sure why.
it should be
H_D 10
G_D 10
GC_D 14
and that'll make it run right. for some reason when GC_D was twice that of G_D it would refuse to make a diagonal path up.
Posted on 2004-05-23 21:06:22
|
Mythril
|
Superneat! :D
Posted on 2004-05-24 23:24:30
|
geronimo
|
hey ragecage. i wonder what it'd be like if you made it find the path starting from the destination and going to the character. that way when the player clicks on a place that isn't reachable the pathfinder will return quickly instead of trying the whole map. or was it just the whole screen? if so.. yikes? less tiles on-screen, heh
Posted on 2004-05-25 01:13:44
|
RageCage
|
hmm, thats an interesting idea... very logical... it also makes writing the path nicer cause the way I did it, you have to kinda backpedal to find the path. And yeah, it would search the entire map before giving up, assuming you ignore the timeout.
I'll try your idea right now
Posted on 2004-05-25 01:20:45
|
RageCage
|
downlaod newest version
I did your idea(and within 35 minues of your post I might add), I'm amazed that more people havent thought of doing it that way. I musta read 5 or 6 articles of A* and not one said to do that. good job.
Also I left the debug on so that you can have a reason to download it and actually see what it does from a visual perspective... it's pretty cool ^_^
(EDIT: found a small bug, the system might just stop if you start trying to get to the map corners. This is because the MAP_WIDTH and MAP_HEIGHT values are too low, increase em and it'll stop doin that.)
Posted on 2004-05-25 01:48:40 (last edited on 2004-05-25 02:05:25)
|
Zip
|
Funky, I like your debug. Interestingly, the pathfinder is now bad at getting out of tight spaces. Try wandering to the end of the one just below where you start and click the other side of the wall. Don't suppose it's possible to play with the weightings to get the path to like following walls round?
Very nice work by the way.
Zip
Posted on 2004-05-25 02:48:29
|
RageCage
|
hmm, well its working the same as if you were on the other side trying to get in... theres nothin I can do about that. as for hugging walls... its an interesting idea but I dont think I'll be doing it anytime soon
Posted on 2004-05-25 03:14:41 (last edited on 2004-05-25 03:22:33)
|
Buckermann
|
Hi RageCage;
I'm using your A*V1.2 function, and it generally works great.
But I having difficulties finding the movement costs after the function found a valid path.
Let's assume my char has only ten movement points to spend, is there a way to see how many tiles the destination is away from the start?
I tried using the "paths" variable, but didn't had any luck with it. It seems like it is changing it's value right after a path is found.
Posted on 2004-05-30 02:02:37
|
RageCage
|
if you really are using v1.2 then paths shouldent be changing untill you try to find a new path, but if its NOT 1.2 then paths would be changing durring writePath... regardless If you'd like to cap the number of entity movements you can change the writePath() to:
void writePath(){
int pastPath;
entPath="";
if(paths > 10) paths=10;
for(pastPath=1;pastPath&ls;paths;pastPath++){
if(path[pastPath].x &ls; path[pastpath+1].x) entPath=entpath+"R"+str(TILES); // right
else if(path[pastPath].x > path[pastpath+1].x) entPath=entpath+"L"+str(TILES); // left
if(path[pastPath].y &ls; path[pastpath+1].y) entPath=entpath+"D"+str(TILES); // down
else if(path[pastPath].y > path[pastpath+1].y) entPath=entpath+"U"+str(TILES); // up
}
}
Posted on 2004-05-30 07:36:37 (last edited on 2004-05-30 07:43:16)
|
