Hi all

I am working to a commercial RTS game like Starcraft and others and i have done a pathfinding algo....

I looks a little like A* but its not

talking about speed i wanna tell u all that i work in ASM so i get the Maximum speed possible and i have a P2/400 /128M
and still a corect fast A* with no lists (for speed i use big matrix) its still too much slow on a 256x256 cell map

So the word is out:

YOU MUST OPTIMIZE IT TO WORK today....

There are many optimizations in doing A* like algo or other alogos and this is all that pros will do...they think and rethink the game they make so they can make outstanding optimizations....

Optimizations makes the difference....

And dont wait for a pro to tell u how he did it....
1.It may not work for u
2.He cant tell u if he wants to make some money

Pros will eventuallu show u the way but they CANT walk it for you

in the end consider what will u make if u have diffrent size units on same map ? eh?

non-pro answer is he will divide the map in 2x2 cells and then he will wonder why his units dont walk like in Starcraft....and sit to such distance one from the other

i have been there....

Bogdan

PS Beandog

i think u have my RTS demo ...

Check my pathfinding..... its a kinda of A* in my own way and it works at about 50fps is it not?

optimizations do it (not ASM code belive me it was 0,5fps in the start)

Bogdan

Actually, I don''t have your demo. But I do know what you mean with different sized units on the same map - but I handled it all right. What is the URL to your demo?

PS is it worth it to have a separate thread emptying a pathfinding queue, to keep the game running smooth despite hefty pathfinding? My game runs at a smooth 30 FPS on my P233/128MB/Banshee at 800x600x16bit with the # of pathfindings per frame as it is (by the way, I''ve got most of the kinks worked out, its kinda messy but works fast), but would it be better with multithreading?

PS Please dont start arguing too much about multithreading v. normal procedural stuff. I''ve heard enough of that. In the end, though, Windows does about 50-60 threads at a time anyway, whats another one going to do?

Well, I think you''ve answered your own question here. If you''ve no problem with the overhead of threads and you''ve got the coding kinks worked out then you can only try it and see.

However, surely windows isn''t running 50-60 threads at the same time your full screen game is playing? I have no idea of the number but I''d imagine it''s not running that many. And have you seen the jerkiness of Windows when it''s running multiple threads and program switching? Not good for a game.

Mike

quote: Original post by Geta

And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric

What do you mean, added support for iterators? I keep redoing my pathfinding as I can never seem to get a good balance between clean code and good speed

quote: Original post by Kylotan

Original post by Geta

And for anyone who happens to develop in MSVC++ or Metroworks, I might suggest that you look into using the Standard Template Library (STL) queue container class for a priority queue. I modified it to be a pathing queue by just adding support for iterators (very easy to do) to the queue class object. It has turned out to be blazingly fast, and extremely easy to work with, as an OPEN list.

Eric
(end of Original post by Geta)

What do you mean, added support for iterators? I keep redoing my pathfinding as I can never seem to get a good balance between clean code and good speed

Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.

If not, then you may want to read a tutorial book on the STL or search the web for an online tutorial. STL comes with MSVC++ and the Metrowerks Codewarrior compiler dev studios (and probably other compilers too) and is well worth learning about.

Eric

BeanDog, didn''t you read the posts on your last thread? If you divide that 1/20 of a second for many frames, your game doesn''t stop or slow down even if you move tens of units simultaneously. The only problem is that the units you''re trying to move, start moving a bit later than you actually click the screen. But it really doesn''t matter at all.

As far as I recall, it took some time for units to start moving even in C&C and Red Alert. And probably in Starcraft, too. Everyone is dividing AI routines into many frames.

And the search algo I think is used in C&C and Red Alert, is the Best First. This is just like A* but you always move the node that is closest to the goal (which one is closest, is approximated by simple airway- distance to the goal). Best First is actually really fast and it produces reasonable routes.

ps. I sent that region search idea

-Hans

quote: Original post by Geta

Are you familiar with the STL container classes?

If so, then you should know what iterators are, and that the STL queue container class does not support them. I derived a pathqueue container class from the STL queue class and modified the pathgueue container to support iterators.

I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I''m just asking for a little more algorithmic detail here

In fact, isn''t there a dedicated priority_queue adaptor in the STL? For some reason I couldn''t use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?

quote: Original post by Kylotan

I thought that queue was technically just an adaptor for the deque class? And therefore if you needed iterator access, why not just use the deque anyway? I was more interested in how you used the iterators, as I pretty much just add things to the queue and pop them off the front. Why do you need iterator access to the queue? I guess I'm just asking for a little more algorithmic detail here

In fact, isn't there a dedicated priority_queue adaptor in the STL? For some reason I couldn't use it for my A* implementation - I think it was the problem of needing to be able to delete from the inside, which could be why you use iterators?

deque and queue are actually separate classes in STL. From what I know, queue is not just an adapter for the deque class, as it can be used with any other container class.

Iterator access to the open list (my pathqueue) was needed for
deletions from the inside of the list.

I forget exactly why I chose not to use the priority_queue adapter (this decision was made in 1997) and instead I choose to modify the queue. My guess would be, that I looked at the source code of both, and I felt that it was easier to modify the queue to do what I wanted, than to use the priority_queue adapter.

Eric


Edited by - Geta on June 22, 2000 9:23:16 AM

Yes, I believe the priority_queue adapter inhibits access to any element except the top one, so modification of the open list (as A* requires) is not so practical with that implementation.

Out of interest, what data structure do you use for your closed list? I think I use some sort of mapped-bitset (just a minimal-storage hash table, I guess), but I don''t recall if that is actually in my A* implementation. (I have a few different pathfinding algorithms implemented and I''m not at my home computer )