//****************************************************************************//
//**************** Intro to Pathfinding - January 14th, 2019 ****************//
//**************************************************************************//
- Alright, further on we go!
- Professor Riedl is fiddling with the OneNotes, while I'm...sitting. Standard pre-lecture position.
- 3:04 - the fiddling continues
- "Apologies for the delay - the smartboard pen wasn't working, but luckily I remembered by iPad. For once."
- A number of people just got added thanks to some last-minute TA signups - "congratulations, you survived the Hunger Games version of phase II"
- Homework #2 (cleverly named "homework 3") will be released on Wednesday
------------------------------------------------------------------------
- Alright, so we're talking about how game AI is done in the industry, large studios, etc.
- For MOST games, AI is broken up into 2 main components:
- Making decisions (combat planning, behavior trees, etc.)
- Moving things around/pathfinding (bots, etc.)
- These are the "pillars" of most game AI
- "Arguably pathfinding is just a subclass of decision problems, but it's so important that it's often treated as its own thing"
- For the first part of the class, we'll assume that there's some magical algorithm that handles decision making for us, and focus on the second of these: pathfinding
- ...but first, let's dig down a little bit into these problems
- First up, let's talk about decision making
- We call the BEHAVIOR of an agent the visible/observable actions of an entity
- "Your AI might be having a deep existential crisis, but all the player sees is a bot staring into a wall until he shoots its head off"
- Some examples of behavior:
- Moving a pawn in chess
- Speaking to a character
- Moving to a position
- Shooting at something
- Decision planning is just trying to answer the question "What behavior should I do now?"
- Oftentimes, this takes the form of BEHAVIOR PLANNING: a sequential problem where the right thing to do might depend on what states we can reach in the future, which might require several steps to reach
- Pathfinding, on the other hand, is where we try to figure out HOW to get somewhere after deciding to move
- Really, pathfinding IS just a form of behavior planning, but it's so common that we break it off into its own special group
- "Doing pathfinding poorly is the fastest way to break a player's immersion - you'd be surprised at how many hours game developers spend working on pathfinding"
- To do pathfinding well, we have to think about 2 things:
- Representations of the world we can use to plan
- Algorithms to manipulate those representations
- Think about the game world (for now) as a 3D, continuous environment - well, dealing with continuous spaces is HARD
- So, to make this easier, we can discretize the environment into pieces we can understand - our representation!
- Robotics has the advantage that movement doesn't have to look
"realistic," but games have the advantage of total information about the world
- There are 2 common representations/"topologies" for doing this in games: grids and path networks
- GRIDS are where we split the space up into a set of discrete squares, bit masking the obstacles so that any grid cells with obstacles in them are marked impassable
- The pros are that grids are simple to deal with (one agent per square!), are very good/performant for large numbers of agents (e.g. RTS), and A* works really well on it (difficult to create "fake shortcuts" in a grid)
- The cons are that grids waste a LOT of space (obstacles take up more space than they should, redundant cells, etc.), agents are confined to cells and cell-based movement (which can look quite robotic, although smoothing is possible), there's a lot of nodes in the search space (which can tank the performance of A* and others), and the discretization is simply too "gross" - it's too obvious that the agent is using a grid
- "So, grids are sometimes okay, but often not the best idea"
- PATH NETWORKS are a grid alternative that tries to conserve a sense of continuous space
- Basically, we have a 2-tier navigation system: a local/continuous system (deals with simple/nearby environments), and a remote, discrete system (deals with complex/far-away environments - basically a sparse network of waypoints)
- So, we'd have a set of waypoints placed strategically throughout the map
- If we're within a certain radius/"bubble" of a waypoint (or have line-of-sight to the waypoint), we know there're no nearby obstacles and can use our local system; if we want to go outside the bubble, we need to use the discrete system instead
- "It's like how when you're in your neighborhood, you'll use your local roads, but if you're traveling to Chicago then you're going to get on the highway until you get back into the neighborhood roads"
- Airplane navigation systems also use a similar technique
- The pros here: compared to grids, there are a LOT less nodes (meaning A* works even better), and movement seems more natural
- So, path networks seem great, but they leave a lot of questions unanswered:
- How do we do continuous local movement (i.e. "steering")?
- How do we follow the path network?
- Where/how do you place the waypoints?
- Which waypoints should be connected?
- Too many waypoints, and our branching factor (O(b^n)) goes up, and performance goes down; too few, and the agent won't move around realistically
- "Right now, the homeworks give you all the waypoints, and you just have to connect them - in the next homework, you'll have to deal with actually placing the waypoints themselves"
- So, a pretty common way of handling local continuous movement is STEERING
- Here (at least for our game engine), the agent has an x/y position, an angle it's pointed in, a current speed, and a max-speed
- To move, the agent will then interpolate along a direction vector at a given speed (e.g. move X pixels forward)
- To turn, the agent will interpolate the change in its angle position (based on its turn speed)
- Putting them together, though, is HARD - we're moving forward and rotating at the same time, so the agent can end up "orbiting" the spot it wants to get to, and we have to calculate where the agent will end up
- To avoid this, we'll usually do movement and turning independently of one another - instead of trying to ONLY move forward and turn appropriately, we'll let the AI strafe sideways/at an angle, and then just rotate so it looks okay
- "Fortunately, humans aren't cars, so this looks pretty believable for most games. Racing games usually end up doing some clever tricks to get around this."
- Alright, Homework 3 will become a debutante on Wednesady - I'll see you all there (here (you know what I mean)).