A* in a real time strategy game

[Kianis]

I got inspired by the topic about remaking Dune so I started this project. It's just for fun though, I doubt flash can handle the pathfinding, scrolling, AI, etc..

There's no scrolling so far, just the pathfinder. Works pretty okay for now, with a tiny map and fog of war but no other units.

asd

I'm not sure the A* works properly though. It doesn't seem as it always selects the shortest path. :/

Edit: new version. Fixed heuristic. No more bugs. Terrain costs works but isn't balanced so the unit often walks over them anyway.

[mike83]

Nice work, it looks pretty fast. Did you write your own A*?
BTW, you should use something else like robust tracing (no idea how it works but looks fast) or even precalculated paths. A* is just too slow, no matter how efficient and optimized.. Then if you limit the size of the map and the number of units you could probably pull it off.

[SaphuA]

Hey,
Is that your own A*-engine? Very nice It seems fast enough..
Although it's pretty buggy, like you say, it doesn't always take the shortest path. It seems like it's also not seeing the different type of terrains (the swamp tiles). Also sometimes it's not reacting or just giving a 'no path' when I click somewhere.

Still nice though

SaphuA

[Kianis]

Thanks,
yes I wrote it after this excellent link.

Seems as if there are quite a few bugs left. :/

I was thinking of limiting the length of the paths to about one screensize and of course there would only be one unit searching for a path at the same time (I've already got a que), but I'll have a look at robust tracing

Edit: After reading a bit about robust tracing I think it might be the better alternative. Terrain costs isn't that important - at least not as important as speed. There's a lot of talking about Klas Kroon's robust tracing. I found a .swf at his site but no .fla?

[Hasufel]

Funny thing, sometimes the character goes, then goes backwards, as if the a* was recalculated.
You didnt include costs it seems ?
The char goes on "slow" tiles as if it liked them

Also, you should accept a click while the char is moving,
its a shame one has to wait until the char is done moving to tell it a new destination.

I tried one A* version some time ago, you can find it here:
http://www.ventoline.com/basis2.html

Keep it up.

[Kianis]

Yep, sorry for not being clear; when I said it didn't take the shortest path I meant on explored terrain. Unexplored terrain is treated as walkable until proven otherwise and it will have to recalculate.

Edit:
> The char goes on "slow" tiles as if it liked them

Haha You're right. Must have done something wrong.. :S

[Kianis]

Updated :P
link

The pathfinder seems to work well even with several units. I think I'll stick with A* since terrain cost is quite imortant after all.

I'll add the tilescrollingengine in a few days.. : )

[UnknownGuy]

If it matters, in games like Warcraft I believe the units already "know" the map, predicting there path without surprise rivers etc....
Hope that helps!

[Kianis]

Originally posted by tonypa
It doesnt work correctly when several units try to walk into same spot same time. They will block each others paths and I lost 2 units because they walked off the map.

Fixed : )