Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


#ActualHodgman

Posted 18 September 2013 - 08:23 PM

I did this back in a Half-Life 1 mod, around 2004, in what's probably a pretty outdated way laugh.png

As the players and bots moved around the level initially, they'd periodically create "waypoints" as they ran/jumped around the place. These waypoints would then be stitched together into the nav-graph and saved for pathfinding purposes.

 

As a pre-process, I'd perform a whole lot of computations on the waypoints, which involved doing a ton of raytracing from each waypoint to every other waypoint. This would involve tracing rays from the "head"/"eye" location of one waypoint to scattered positions throughout the whole "body" volume of the other waypoint, to see how much of a persons body would be visible if you were standing there.

 

I'd also run Dijkstra's algorithm and count how many paths went through each waypoint to get an estimate of traffic.

 

From these results, I'd determine the best direction to face when camping at a waypoint, how visible you are, how much cover you're in, if you're in a choke-point, a wide-open space or a corner, etc... And then from those I'd determine some dependent heuristics, such as how much cover the waypoints that can see you are in, if you're overlooking high traffic areas, if you're overlooking a choke-point, etc...

 

Many of those heuristics were unbounded (e.g. count the number of visible waypoints from here), so at the end, I'd normalize all the data into the 0.0 - 1.0 range.

 

From there, I'd use them as fuzzy-logic booleans to calculate some higher-level properties, such as "is this a good sniping spot" -- which might be defined as something like SelfCover * (1-SelfWideOpen) * VisibleTraffic * (1-SelfTraffic) (or you're in cover, not in a wide open area, you're looking at a high traffic area, and you're not in a high traffic area).

 

There's a visual overview of the results here: http://www.youtube.com/watch?v=68Rb1r8N9j4

 

[edit] I've since lost the code in a hard-drive crash, but I found the article that I based this approach off:

http://www.gamasutra.com/view/feature/131447/terrain_reasoning_for_3d_action_.php?print=1


#1Hodgman

Posted 18 September 2013 - 08:17 PM

I did this back in Half-Life 1, in what's probably a pretty outdated way laugh.png

As the players and bots moved around the level initially, they'd periodically create "waypoints" as they ran/jumped around the place. These waypoints would then be stitched together into the nav-graph and saved for pathfinding purposes.

 

As a pre-process, I'd perform a whole lot of computations on the waypoints, which involved doing a ton of raytracing from each waypoint to every other waypoint. This would involve tracing rays from the "head"/"eye" location of one waypoint to scattered positions throughout the whole "body" volume of the other waypoint, to see how much of a persons body would be visible if you were standing there.

 

I'd also run Dijkstra's algorithm and count how many paths went through each waypoint to get an estimate of traffic.

 

From these results, I'd determine the best direction to face when camping at a waypoint, how visible you are, how much cover you're in, if you're in a choke-point, a wide-open space or a corner, etc... And then from those I'd determine some dependent heuristics, such as how much cover the waypoints that can see you are in, if you're overlooking high traffic areas, if you're overlooking a choke-point, etc...

 

Many of those heuristics were unbounded (e.g. count the number of visible waypoints from here), so at the end, I'd normalize all the data into the 0.0 - 1.0 range.

 

From there, I'd use them as fuzzy-logic booleans to calculate some higher-level properties, such as "is this a good sniping spot" -- which might be defined as something like SelfCover * (1-SelfWideOpen) * VisibleTraffic * (1-SelfTraffic) (or you're in cover, not in a wide open area, you're looking at a high traffic area, and you're not in a high traffic area).

 

There's a visual overview of the results here: http://www.youtube.com/watch?v=68Rb1r8N9j4


PARTNERS