A* pathfinding

just posting a WIP shot of my pathfinding system.
Right now its pretty slow, im improving it.
The end result will have smooth turn and also shortest path in euclidean space (means no zig zag)

The second image shows your discretization of euclidean space?

Sample test map?

edit: I think WC3 units can move only between squares so straight movement is absolutely compromised in WC3. The system only solves pathfinding, I tihnk; and an application of this would be to approximate 'proper' movement - under the above-mentioned constraint - and to ameliorate wc3 pathing AI.

im working on making it straight movement + smoothing. And this system was made cus i wanna use MaDOS to allow custom movement...

damn xD now i want to try it self...
<3 tnx for the idea.

and yeah do you use wc3 pathing ?

ye i use wc3 pathing to avoid wc3 obstacles, but u can also declare ur own virtual nodes tat is unwalkable or mountains etc

I created a A* pathing for my Battle Tactics map, It works well :)

1) What does "A*" denote? Or what do "A", here, and "*" each denote?

2) Can you explain how you'll override current WC3 by-square movement, to apply/simulate straight and smooth movement? I am just intrigued. Or, just, how will you override current WC3 movement, even adding to it that customizable pathing feature?

Is this founded on IssuePointOrder("move")?

If it is, how then do you override current WC3 pathing? If it isn't, how do you simulate movement (with animation, pathing, etc.)?

i'm pretty sure A* is the one where you branch out all the nodes until you reach the destination, and then read them backwards to get the shortest path.

Isn't that 'bothersome'? Is that the only plausible method?

programming is bothersome to begin with :) Yes u have to check every each closest node and find ur way. And A* is known as the best/popular method^{[citation needed]}.
Im doing this for learning, it wont do any much different from current wc3 pathing accept tat i can customize it alot, such as smoother movement etc. Nice for cinematic maybe :D

http://en.wikipedia.org/wiki/A*_search_algorithm

=( boring... to create own alogorithm is awesome ^_^

Then i suggest u build a new computer system, cus using something already invented is boring :D
Btw most of the A* algorithms u find around are the basic, but they are not effective, and is slow (like the wikipedia one)

if the goal is finding the shortest way possible so it's ofc will be slow... cause you will do precalculations to avoid wrong paths...
thats true ^_^

may personal opinion is what it's useless in wc3 playable maps (ofc if it's not build around this movesystem)
+ it wouldnt fit really well into a cinematic imo... it's simpler and better to make checkpoint system or something similar.

and yeah it's useless cause of the affordable resources to calculate the path.
if it would be possible to make it stepwise (with out extra calculations) it would be usefull. (but also not really much)

i imagine if you would target the other end of the map O_o or is there some bad as trick optimisations which doesnt allow to to calculate such large/long paths ? and does split it... but it wouldnt be correct at all so.... hmmm

*we want a demo map* to check perormance...

It is also impossible. Shortest paths is one of the oldest problems in programming, it doesn't matter what sort of lame idea you can come up with to solve this problem, someone already had that idea.


Err, that describes like 10 standard pathing algorithms.

You can't change the algorithm itself, just the implementation, since A* is heavily dependent on that heuristic to work, then different heuristic will greatly change the algorithm - Do you want it to take ages but be very accurate? Or do you want it to be very fast and inaccurate?

Unless the pathing is dynamic, then precalc is the obvious solution. Dynamic pathing? I am quite sure blizz uses some sort of dynamic A* already, but it is too focused on speed hence sometimes the pathing algorithm will do dumb stuff when the terrain varies too much... It made sense since the player is able to correct those issues anyway...

Edit: Seriously the wikipedia one is fast enough, that is unless you implement the "x := the node in openset having the lowest f_score[] value
" part naively.


Err, no?