• Advertisement

Archived

This topic is now archived and is closed to further replies.

RTS and Path Finding

This topic is 5097 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

If you had like a city of buildings and you had vehicles the move around and carry stuff how would you program them to find there way to a certain building then go into a "loading platform". I can program this do just do that but then the vehicles go through the other buildings too. heres some of my theory code:
//point = .x,.y

//v = Vehicle


void CVehicle::Navigate(point dest)
{
if (vlocation.x > dest.x)
go left;

//now would i check for a collision with a building now or ?


}

Share this post


Link to post
Share on other sites
Advertisement
You already know the term "pathfinding", so I don''t need to tell you that that''s what it''s called. Google for the term and you''ll find reams of helpful information.


"Sneftel is correct, if rather vulgar." --Flarelocke

Share this post


Link to post
Share on other sites
A* is the most basic pathfinding algorythm of all times. And by pathfinding I mean ''wont go into dead ends''. Pretty much, it just radiates outwards the possible places it could go. Aka:

std::set< state * > checked_possible_states;
std::set< state * > unchecked_possible_states;
state * solution;
bool done = false;

unchecked_possible_states.insert( current_state );

while ( !done ) {
std::set< state * >::iterator checkstate = unchecked_possible_states.begin();
while (checkstate != unchecked_possible_states.end()) {
if (*current_state->is_there()) {
done = true;
solution = *current_state;
//make a list of where we came from
break;
}
if (*current_state->can_turn_left() && not_allready_checked( *current_state->turned_left()) ) {
unchecked_possible_states.insert( new state( *current_state->turned_left() ) );
}
if (*current_state->can_turn_right() && not_allready_checked( *current_state->turned_right())) {
unchecked_possible_states.insert( new state( *current_state->turned_right() ) );
}
if (*current_state->can_move_forward() && not_allready_checked( *current_state->moved_forward())) {
unchecked_possible_states.insert( new state( *current_state->moved_forward() ) );
}
checked_possible_states.insert( *current_state );
unchecked_possible_states.erase( *current_state );
}
}
if (solution) {
state * addstate;
std::slist< state * > path;
while ( addstate ) {
path.push_front( addstate );
addstate = addstate->previous_state(); //assuming return of 0 for the original state
}

//cleanup: delete anything on the (un)checked_possible_states set if it isn''t on our path.

return path;
}
else {
throw "Error: no pathway";
}


note that the moved_forward & turned_left/right functions would set an internal previous_state variable.

The most basic A* practice example is to create an array representing someplace. Put some walls in this place (represented by a same sized array)... and another array that keeps track of wheither the cell has allready been visited, and if it has, which cell it was visited from.

Allow the thing in question to move up, down, left, or right. Add a start location and end location. Run the pathfinding algorythm. Volia.

-Mike

Share this post


Link to post
Share on other sites
Well, depending on how your your city is designed you might be able to do some tricks. Is your city rather free-form, build where ever you like, no roads? (Kinda like a Starcraft city.) Is you map in 3D? Well even if it is 3D rendered most RTSs you view from top down... anyway...

If you can create waypoints around your buildings, link those waypoints into a graph. Include your vehicle's current position as a waypoint. Then run your favorite shortest path algorithm to get from your current position to the dock. When you are linking waypoints, do your collision detection, because in order for two waypoints to be linked there has to be a free path. It gets tricky if there are other moving objects on the screen though.

Waypoints on an RTS wouldn't be the end-all solution, but maybe they will be helpful to create detour routes, and avoid running collision detection every update.



[edited by - Scint on February 5, 2004 10:35:57 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
quote:
Original post by MaulingMonkey
A* is the most basic pathfinding algorythm of all times. And by pathfinding I mean ''wont go into dead ends''. Pretty much, it just radiates outwards the possible places it could go. Aka:



I''m sorry, that''s breadth-first search. Not A*.

Share this post


Link to post
Share on other sites

  • Advertisement