RTS/RTT style Pathfinding (using IanM's A* search routine)

Author

Message

Dia

19

Years of Service

User Offline

Joined: 16th Jan 2005

Location:

Posted: 27th Apr 2010 17:17

Link

For anyone who has looked into IanM's A* Snippet, then hopefully this should be a quick one:

I have buggered around with it enough that I can get it working in 3D for a single unit, the only query I have is what is the best way to use it for multiple units?

Is it best to give each individual unit its own seperate waypoint array (I didn't even think it was possible to have an array inside a type, and thats how all of my unit data is arranged)

alternatively, is it better to have the waypoint array as a seperate entity that can just be cross referenced

...or is there a third (and probably better!) way that I haven't thought of yet?

This is not the Sig you are looking for....

Back to top

Profile PM

IanM

Retired Moderator

22

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 27th Apr 2010 21:23

Link

The library handles the provision of different paths already (using CreateSearchPathList with the number of paths you wish to have available), so you only need to store the ID of the path for each entity and let each entity follow its own path. You could also attempt to check for proximity to an existing path so that the paths can be shared, but only do that if the pathfinding is too expensive to carry out too often.

The real problem is to stop your entities overlapping each other while following similar or identical paths, and that can usually be dealt with using standard DBPro collision in most cases.

Utility plug-ins collection (updated 02 Mar 2010) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Dia

19

Years of Service

User Offline

Joined: 16th Jan 2005

Location:

Posted: 28th Apr 2010 14:12

Link

ahhh gotcha, now I understand why it was "CreateSearchPathLists(0)" rather than putting an actual number in there

what I was also trying to sort out was whether or not is is worth keeping ALL of the pathing data for each individual, or maybe just the 1st two or three nodes.

I figure that considering the pathfinding will be called every 'n'th cycle, and being updated only then, would it really save me anything (I know that the whole path is generated anyway, so maybe not)

Anyway, thanks heaps for the response!

This is not the Sig you are looking for....

Back to top

Profile PM

IanM

Retired Moderator

22

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 28th Apr 2010 15:39

Link

Considering the high cost of pathfinding, I'd keep the path until I was done with it rather than regenerate frequently after using a few nodes.

I think that at some point I'll combine it with function pointers and coroutines from my plug-ins, and have a pathfinding that will automatically suspend the current search and resume searching when you tell it to. That should allow you to control exactly how much time is spent per frame of pathfinding.

Utility plug-ins collection (updated 02 Mar 2010) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Dia

19

Years of Service

User Offline

Joined: 16th Jan 2005

Location:

Posted: 29th Apr 2010 14:05

Link

yeah I guess, only problem is that I (intend to) have a fair few dynamic objects in the way i.e. destroyable walls, moving doors etc.

handling them with normal collision routines looks kinda tacky, so I was looking at periodically running a search again (once or twice a second or so) to avoid them in their new or destroyed state. Will continue to play around I guess

Thanks!

This is not the Sig you are looking for....

Back to top

Profile PM