   RTS and Path Finding
  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 = Vehiclevoid CVehicle::Navigate(point dest){if (vlocation.x > dest.x)go left;//now would i check for a collision with a building now or ?}
  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 ;  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 ;  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];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*.