JoJoBo wrote:Do you have your own map editor or how do you generated the worlds ?
The landscapes are built with
Ogitor Scene Builder
JoJoBo wrote:How do you manage enemy movement and obstacle avoidance ? for example with structures or trees ?
Do you use some special library or terrain map navigation or something else ?
I went old-school with my pathing. I use a path-node based approach. I'll describe this in a little more detail. But before I go on, path-node pathing is generally considered inferior to the more modern nav-mesh pathing, such as that implemented by
recast detour. However, A* path-node pathing worked pretty well for me, and I was more comfortable working with this, given my limited time to devote to it.
So, first I construct my path map:
1. Every quad on the landscape is assigned a path node.
2. I determine if a path node is walkable by checking the slope of the terrain at that point, and also check to see if anything (like a rock) is obstructing that path node.
3. I solve paths using
micropather, which is just an A* path solver, but it's very fast.
But A* path-node pathing is really just the start. It will tell you how to get from point A to point B, but it probably won't look good, as your AI characters zig-zag from path node to path node. So there are a ton of optimizations over the basic path-node chasing.
Examples:
- if the AI character passes a "line of sight" check to its target (using a physics raycast query). then I just run directly towards it. (It's actually a little more complicated than this, but that's the general idea).
- i detect if the AI character gets stuck (say on another AI character) by checking if the AI is trying to move, but remains in the same general position for too long. If stuck, I go into a separate "get unstuck" pathing routine.
- the AI troops will do other things than just chase after their target. For example, AIs are aware of cover positions, which they may try to stand behind and use to their advantage, as a player would.
- you don't always want to path to your exact target's position, but sometimes somewhere nearby to shoot at it.
Code-wise, I arrange all my basic pathing functions in a single system called the PathSystem. Then, I have AI tactic code which calls into this path system, depending on what it's trying to do.
My AI tactics have names like:
Code: Select all
MeleeMonster_TacticSequenceType,
ChargeTarget_TacticSequenceType,
TakeCoverAndAttack_TacticSequenceType,
PursueAndAttack_TacticSequenceType,
StandAndFire_TacticSequenceType,
StandAndMelee_TacticSequenceType,
StrafeAndFire_TacticSequenceType,
Flee_TacticSequenceType,
ShootRocket_TacticSequenceType,
ThrowBomb_TacticSequenceType,
UseStim_TacticSequenceType,
UseShieldGun_TacticSequenceType,
ConstructTurret_TacticSequenceType,
MechLaunchRocket_TacticSequenceType,
And just for anyone with way too much time on their hands, here's my PathSystem.h API, so you can see generally how I structure things. My game is closed source, but I don't mind talking about how I did things. No anti-singleton rants, please.
Code: Select all
// Copyright (c) 2011 Firedance Games Inc
#ifndef __PATH_SYSTEM_H__
#define __PATH_SYSTEM_H__
// base class
#include "micropather/micropather.h"
#include "XML.h"
// ogre
#include "OgrePrerequisites.h"
using namespace Ogre;
// std
#include <map>
#include <vector>
// game
#include "ActionType.h"
#include "ChaseResultType.h"
#include "FactionType.h"
#include "MID.h"
#include "PathResultType.h"
// prototype
class ActorUserData;
class Decor;
class Landscape;
class Mobile;
class NxActor;
class Person;
class Ship;
// The PathSystem is the sister system of the FlightSystem.
// - The PathSystem is used for traditional pathing on a terrain.
// - The FlightSystem is used for 3D maneuvering in space.
// - See IndoorClassSystem.h for pathing inside a space station or other indoor structure.
//
// Pathing consists of 2 primary techniques:
//
// 1. "Straight Chase" Pathing
//
// - When there is a direct line of walkable terrain between the AI and its
// target, we will walk that direct line.
//
// - This is the preferred technique, because it's cheaper, and looks better.
//
// - If the target goes temporarily out of "straight chase" visibility, we
// don't immediately give up the straight chase. Instead, we remember where
// our last good "straight chase" target position, and move towards
// that instead. This is a very good optimization - it often allows the AI
// to catch up with the target and re-achieve "straight chase" visibility.
//
// 2. A* Pathing
//
// - we use some middleware called "MicroPather" to implement our A* solver.
//
// - Good things about MicroPather:
// * simple: one include file, one cpp file, no external libs/dlls
// * flexible: it allows you to implement your own graph data structure.
// This worked out well with how I used terrain heightmap data to form a
// graph out of walkable surfaces.
// * focused: written and optimized specifically for real time path planning
// in games.
// * I also looked at the boost graph lib. It was a highly templated generic
// solution for all sorts of graph problems. It would have been much more
// tricky to integrate, harder to debug, and possibly slower due to the
// way it was written to support many different graph problems.
//
// The PathSystem works very closely with:
// - class PathData: Pathing data which gets cached on an AI (e.g. the path nodes leading to a target.)
// - class PathMap: The graph of walkable terrain, owned by class Landscape.
// See discussion in PathData.h and PathMap.h
//
class PathSystem : public micropather::Graph, public XML
{
//
// System Singleton
//
public:
PathSystem();
~PathSystem();
// Create the singleton instance
static void Create();
static PathSystem* GetSingleton() { return s_pSingleton; }
private:
// There can only be one instance of a singleton
static PathSystem* s_pSingleton;
//
// Lifecycle
//
public:
void Init();
void Tick( float i_fSecFrame );
//
// Loading and Saving Game State
//
public:
// Loads data from a savegame file.
// Savegame files are XML, and we are passed an XMLNode pointing to the data for this system.
// This function is called either when we begin a new game, or the user loads a saved game.
void LoadGameState( XMLNode& i_node );
// Writes data for a savegame file.
// Savegame files are in XML format, so we return an XMLNode containing all game state data for this system.
// This function is called whenever the player saves the game.
XMLNode SaveGameState( const char* i_szNodeName ) const;
// Reinitializes all data back to the initial state of the system, to make sure that no data "leaks through"
// (persists) from a previous game to the new game.
// This should only ever be called by the LoadSaveSystem when we're loading a game.
void ClearGameState();
//
// AI Calls
//
public:
// This is the high level API you want to use to make an AI pursue a target.
ChaseResultType ChaseTarget( Person* i_pChaser, Mobile* i_pTarget, float i_fDistFound, float i_fSecFrame, ActionType i_eMoveAction = Walk_ActionType, ActionType i_eAvoidAction = Walk_ActionType, Degree i_degMoveThreshold = Degree( 45.f ) );
// Alternate API for chasing a position rather than a target.
ChaseResultType ChasePosition( Person* i_pChaser, const Vector3& i_posTarget, float i_fDistFound, float i_fSecFrame, ActionType i_eMoveAction = Walk_ActionType, ActionType i_eAvoidAction = Walk_ActionType, Degree i_degMoveThreshold = Degree( 45.f ) );
// Strafing
// You can just call this every tick and everything will work out.
// Returns true if we're strafing
bool DoStrafeIfTakingDamage( Person* i_pStrafer ) const;
// A routine to make i_pPerson walk around mostly aimlessly.
void Wander( Person* i_pPerson, const Vector3& i_posHome = Vector3::ZERO, float i_fDistLeash = -1 ) const;
//
// ChaseTarget Helper Functions
//
private:
// The position we should path towards isn't always the exact position of our target.
// Examples:
// - If the target is in an unwalkable position, we should pick a nearby walkable position
// - if the target is huge, we should pick a point somewhere on its periphery.
Vector3 GetChasePosition( Person* i_pChaser, const Mobile* i_pTarget );
// For small objects, this just returns i_pTarget's position.
// For some large objects, such as buildings, this will return a point on i_pTarget's periphery.
//
// The reason for this is because when pathing towards a large target, we will not be able to path
// to it's center, because that point will be blocked by the object's physics. So instead we
// need to find a clear point around the edge of the target to path to.
Vector3 GetLargeObjectPeripheryPoint( Person* i_pChaser, const Mobile* i_pTarget );
// Helper for GetNearestPosition
bool InqWalkablePeripheryPoint( Person* i_pChaser, const Mobile* i_pTarget, float i_fRadius, Vector3& o_posNearestPeriphery );
Vector3 GetNearestUnobstructedWalkablePosition( const Vector3& i_pos );
//
// Strafing Helper Functions
//
private:
ActionType GetCurrentStrafeDirection( Person* i_pStrafer ) const;
ActionType PickRandomStrafeAction() const;
ActionType GetOppositeStrafeAction( ActionType i_eStrafe ) const;
bool CanStrafe( Person* i_pStrafer, ActionType i_eStrafe ) const;
//
// Obstructions
//
public:
// If i_pMobile has been set as an obstacle (Mobile::m_bPathMapObstacle), then
// it will be added to the PathMap.
void RegisterObstacle( Mobile* i_pMobile );
// This must be called when an obstacle is destroyed or removed from the scene, otherwise
// AIs will keep pathing around the no longer existing obstacle.
void UnregisterObstacle( Mobile* i_pMobile );
// Same as above, except for decor objects.
// Currently, we are not planning on making decor objects destructable, so there is no
// corresponding unregister call.
void RegisterObstacle( Landscape* i_pLandscape, Decor* i_pDecor );
// General code shared between all the RegisterObstacle public API functions.
// - actually we now call this directly from outside the PathSystem for our PagedGeometry entities.
void RegisterObstacle( Landscape* i_pLandscape, NxActor* i_pActor, MID i_mid );
//
// Pathing Techniques
//
private:
// 1. "Straight Chase" Pathing
//
// Note: I pass in i_fDistTarget because usually the caller needs to calculate it anyways,
// and there's no sense in calculating it twice.
//
// Returns true if there is a straight-line chase path to our target.
bool AttemptStraightChaseToTarget( Person* i_pChaser, Mobile* i_pTarget, Vector3 i_posChase, float i_fSecFrame, ActionType i_eMoveAction, ActionType i_eAvoidAction, Degree i_degMoveThreshold, bool i_bForceDetectAttempt = false ) const;
// 2. A* Pathing
//
// An A* path solver between two points on the terrain.
PathResultType AttemptPathToTarget( Person* i_pChaser, const Vector3& i_posTarget, float i_fSecFrame, ActionType i_eMoveAction );
//
// Low Level Pathing Helper Functions
//
public:
// A low level function for turning to face the specified direction.
// Note: i_dirTarget must be localized to i_pChaser.
// Note: i_dirTarget is not const because we normalise it.
void TurnTowardsLocalDirection( Person* i_pChaser, Vector3& i_dirTarget, float i_fSecFrame, bool i_bLimitDirectionSwitch = true ) const;
// Alternate API which takes an absolute position to turn towards.
void TurnTowardsPosition( Person* i_pChaser, const Vector3& i_posTarget, float i_fSecFrame, bool i_bLimitDirectionSwitch = true ) const;
// Helper for TurnTowardsDirection
// This keeps us from gyrating left and right while approximately being aimed at the target.
bool HoneInOnDirection( Person* i_pChaser, Vector3& i_dirTarget, float i_fSecFrame ) const;
// A low level function for moving directly towards the specified position
void MoveTowardsPosition( Person* i_pChaser, const Vector3& i_posTarget, float i_fSecFrame, ActionType i_eMoveAction = Walk_ActionType ) const;
// Returns true if i_pChaser is trying to move, but has been stuck in the same position for a while.
bool IsStuck( Person* i_pChaser ) const;
// Spin and jump to try to escape the stuck position.
void TryToGetUnstuck( Person* i_pChaser ) const;
// As simple as it sounds - a handy function to check if i_pPerson is walking or running.
// If you want to count strafing as walking or running, set i_bIncludeStrafe to true.
bool IsWalkingOrRunning( Person* i_pPerson, bool i_bIncludeStrafe = false ) const;
// Does an LOS check and turns to avoid any obstacles in front of me.
// Simple avoidance logic only - not powerful enough to handle complex paths!
bool AvoidObstacles( Person* i_pPerson, const Mobile* i_pTarget, const Vector3& i_posDestination, float i_fSecFrame, ActionType i_eMoveAction = Walk_ActionType ) const;
// Implements our logic to strafe left or right in response to a collided obstacle.
// See header comments for PathData::SetCollidedPhysicsActor(..)
bool StrafeAroundCollidedObstacle( Person* i_pPerson ) const;
// Helper function for AvoidObstacles
void RaycastForObstacles( Person* i_pPerson, const Mobile* i_pTarget, const Vector3& i_posDestination ) const;
//
// Terrain Queries
//
public:
// Returns true if the given position on the terrain is walkable.
bool IsPositionWalkable( const Person* i_pPerson, const Vector3& i_pos ) const;
// Returns true if the given path node on the terrain is walkable.
// Path nodes are of type void* because of MicroPather integration.
// See PathMap.h, micropather.h, and especially MicroPather docs for more info.
bool IsPathNodeWalkable( const Person* i_pPerson, void* i_pPathNode ) const;
// Returns true if the straight line between the start and end positions can be walked over.
// Parameter i_bNoNeighboringObstacles : See discussion in function body
bool IsStraightLineWalkable( const Person* i_pPerson, const Vector3& i_posStart, const Vector3& i_posEnd, bool i_bNoNeighboringObstacles = false ) const;
// Returns true if there is an adjacent walkable position to i_posStart. If true, returns the adjacent
// position in o_posAdjacent.
bool InqAdjacentWalkablePosition( const Person* i_pChaser, Vector3& io_pos ) const;
// Returns the walkable position if found.
// Returns i_posUnwalkable if not found.
Vector3 SearchForNearbyWalkablePosition( Person* i_pChaser, const Vector3& i_posUnwalkable ) const;
// Returns true if i_pos is adjacent to an obstructed position.
bool IsPathNodeAdjacentToObstacle( int i_iPathNode ) const;
// Returns the number of adjacent obstructed path nodes.
int GetNumAdjacentObstacles( int i_iPathNode ) const;
// Returns the number of adjacent unwalkable path nodes.
int GetNumAdjacentUnwalkables( int i_iPathNode ) const;
// Returns true if this distance is within chasing range.
// Returns false if this distance is too far away, and all pathing activities should cease.
bool IsInPathingRange( float i_fDistTarget ) const;
//
// Cover
//
public:
void RegisterCover( const Vector3& i_pos );
void RemoveAllCoverPositions();
std::vector<Vector3> FindCoverPositions( const Vector3& i_pos, float i_fRadius ) const;
Vector3 AssessThreatDirection( FactionType i_eFaction, const Vector3& i_pos, float i_fRadius, const Person* i_pPerson = 0) const;
bool InqBestCoverPosition( const Person* i_pPerson, const std::vector<Vector3>& i_vecCoverPos, Vector3& o_posBestCover );
void SetUsingCover( const Vector3& i_posCover, MID i_midPerson );
void ClearCover( const Vector3& i_posCover, MID i_midPerson );
bool IsCoverOwned( const Vector3& i_posCover ) const;
private:
std::vector< Vector3 > m_vecPosCover;
std::map< MID, Vector3 > m_mapCoverOwnedBy;
//
// Inherited Graph Functions, from micropather.h
//
public:
// Note: *** THIS IS NOT MEANT AS A PUBLIC API ***
//
// These are all internal helper functions that you don't need to worry about as
// a user of this system. But they must be public because of callbacks made from micropather
// into this system.
// PERF: Consider inlining a bunch of these pathing functions?
// From micropather.h:
// Return the least possible cost between 2 states. For example, if your pathfinding
// is based on distance, this is simply the straight distance between 2 points on the
// map. If you pathfinding is based on minimum time, it is the minimal travel time
// between 2 points given the best possible terrain.
float LeastCostEstimate( void* i_pPathNodeStart, void* i_pPathNodeEnd );
// From micropather.h:
// Return the exact cost from the given state to all its neighboring states. This
// may be called multiple times, or cached by the solver. It *must* return the same
// exact values for every call to MicroPather::Solve(). It should generally be a simple,
// fast function with no callbacks into the pather.
void AdjacentCost( void* i_pPathNode, std::vector< micropather::StateCost >* i_pAdjacent );
// From micropather.h:
// This function is only used in DEBUG mode - it dumps output to stdout. Since void*
// aren't really human readable, normally you print out some concise info (like "(1,2)")
// without an ending newline.
void PrintStateInfo( void* i_pPathNode );
// To convert from a position to a micropather "state" (i.e. PathNode).
// See the micropather docs for more info on states. A state is basically just a unique representation of a position.
void* PositionToPathNode( const Vector3& i_pos ) const;
// To convert from a micropather "state" to a position.
// See the micropather docs for more info on states. A state is basically just a unique representation of a position.
//
// Note: This only returns a 2D position because the state is a 2D x,y coordinate on the heightmap.
// We could return a 3D position if needed. To achieve this, we'd want to cache the absolute heights of all the
// path nodes within Landscape::m_vecPathMap
Vector2 PathNodeToPosition( const void* i_pPathNode ) const;
private:
// We need to record who the chaser is before we call micropather::Solve.
// This is because the graph functions called by micropather::Solve (such as AdjacentCost)
// need to take into account the GetMaxWalkableHeightDistance of the chaser. But, since
// the graph APIs are defined by micropather, we can't pass in the chaser.
// So, we'll just record it in a system variable, then query it from the graph functions.
void SetCurrentChaser( const Person* i_pChaser );
const Person* GetCurrentChaser() const;
const Person* m_pCurrentChaser;
//
// Micropather solver
//
public:
// Not meant as a public API, but leaving this function public, so the ConsoleSystem can access it for testing.
//
// parameter: o_path is an array of pathnode indexes, outlining the path from start to finish.
// Unfortunately, you will have to cast the void* vector values to integer pathnode indexes.
// This is a rough edge with the micropather API.
// See Landscape.h for more info on pathnode indexes.
PathResultType SolvePath( const Person* i_pChaser,
const Vector3& i_posStart,
const Vector3& i_posEnd,
std::vector< void* >& o_vecPathNode,
float& o_fTotalCost );
// For path debugging
void DisplayPathNodes( std::vector<void*>& i_vecPath ) const;
void DisplayPathMap( const Person* i_pPerson, const Vector3& i_posCenter, int i_nNodesPerEdge );
// If we change the PathMap in any way (i.e. costs between path nodes change),
// we need to reset the cached data stored by m_pPathSolver.
// Example: when we add obstacles to the path map.
// See the MicroPather docs for more info on resetting the cache.
void ResetPathCache();
private:
// This gets set by SetActiveLandscape.
// It will be deleted and re-newed as different landscapes are activated.
//
// TODO: It's not going to work to have only one solver, with multiple
// creatures of different PathData:;GetMaxWalkableHeightDifference(). The cache
// will get all messed up.
// This is yet another reason to revisit this cache, and potentially disable it completely.
// Or maybe maintain multiple path solvers for creatures of different height ranges.
micropather::MicroPather* m_pPathSolver;
//
// Active Landscape
//
public:
void SetActiveLandscape( Landscape* i_pLandscape );
void ClearActiveLandscape();
private:
// Cache a pointer to the current Landscape Scene.
// This prevents us having to constantly do a dynamic_cast<Landscape*> operation inside the performance critical
// A* pathing functions.
Landscape* m_pActiveLandscape;
};
// Syntactic convenience function.
inline PathSystem* PathSys()
{
return PathSystem::GetSingleton();
}
#endif // __PATH_SYSTEM_H__