//****************************************************************************//
//****************** Path Networks - January 16th, 2019 *********************//
//**************************************************************************//

- Alright, starting with a quick announcement: John, from VGDev!
    - "Come to VGDev! Make games! Get things on your resume! It's awesome!"
- Hopefully most people have finished Homework 2 by now - "I know pip can be bollocks sometimes" - so we can start moving on towards Homework 3, which'll be released tonight or tomorrow
    - "Homework 3 is really cool, but it can be one of the trickier ones"
    - We haven't gotten to everything you'll need to complete this, but let's go over it anyway
        - When you open up the homework, you'll notice something - there're no path nodes already placed in the map!
            - When you get a solution, you should generate green lines representing the navigation mesh (empty space), and blue lines representing the actual path nodes
        - In general, you'll generate a navigation mesh first, then use that info to figure out where the path nodes should go
        - Then, basically, use your homework 2 solution to create the actual navigation path
            - "This is pretty cool, right? This is automated design - instead of having to manually place all these navigation nodes, we can make an AI to handle it for us!"
        - For full credit, your final path network has to be fully connected, and any valid spot should be reachable by the agent using your network
    - "Once you do that, it should work just like homework 2 - you click on a point, and then it goes in the wrong direction"
- The ANNOYING thing about this homework: the basic algorithm's pretty simple, but the edge cases are VERY annoying
    - "So, DON'T start late - trust me, you won't be able to find all the edge cases if you start 2 or 3 days before this is due, and it'll get really frustrating"
----------------------------------------------------

- Okay, so we've been talking about path networks - these invisible nodes that act like a "highway" telling our agent how to move around the map
    - When we're "close" to a node, though, we don't directly travel on the path network - we just use our local "steering" system
        - In most games, this means we just move, and then rotate to "look" like we're turning instead. In our game engine, we do something even better (read: lazier) - the agents just rotate instantaneously, so we only have to worry about moving

- There's one thing we have to worry about with local steering, though: how do we handle obstacle avoidance?
    - In other words, what if we want to go somewhere but there's some obstacle directly between us and our goal?
        - Well, if it's just the static terrain, we can try to check for obstacles using RAYCASTING - we shoot a line to our destination, and if it's blocked, we'll stop using our local steering system and go via the path network
    - ...but what about movable objects?
        - Back in the 1990s, crates were EVERYWHERE in videogames because square boxes were about the only thing we could easily render. And then one day, some bright terrible programmer wondered what would happen if he made the crate a physics object. This looked AWESOME, but a terrible problem suddenly comes up: what if the CRATE, a dynamic object, falls between us and our goal?
    - We can't just jump on our path nodes after raycasting, since the obstacle might lie right on top of one of our paths!
        - In the old days, bots would literally just ignore crates - raycasts would intentionally go straight through crates, and they would either walk right through them like they weren't there, or they would kick the crates out of the way if they ran into them
        - Another approach would be to jump/climb OVER the crate
            - In HALO 2, large obstacles would have "vault points" attached to them, and when the agent got close enough to a crate in its path it would walk itself in front of one of the vault points, then jump over the crate
                - In this approach, raycasts still ignore the object for pathfinding
            - "This is actually a pretty good solution - the agent seems like it's intelligently responding to the crate, and we don't have to do anything too crazy"
    - But what about dynamic objects too large to convincingly jump/climb over?
        - In this case, the object might have navigation points scattered on it, and if it blocks the AI then the agent will follow those points like breadcrumbs until it can see the path again
            - This isn't done very often - especially because if TWO crates fall next to each other, then it quickly becomes a non-trivial thing to navigate around both of them without getting in a loop

- The point is: static objects let us pre-generate these nice paths, but dynamic objects aren't accounted for, so we have to deal with them on the fly

- Another point: things are nice and straightforward until you start dealing with the edge cases
    - A few edge cases we have to worry about with steering:
        - CLIPPING is when our agent goes too close to an obstacle and tries to walk through somewhere that it shouldn't be able to reach; there are basically 4 ways of dealing with it
            - Parallel raycasting is when we shoot 2+ parallel rays that cover the width of our agent - this means, if both those rays hit, we're more than likely in the clear!
                - What about skinny objects, though? What if there's a lightpole that our raycasts completely miss? There are 2 solutions to this:
                    - Don't put really thin objects in your map
                    - Do 3 raycasts
                - "This solution works just fine for homework 2"
            - Use MATH! In particular, the minimum distance calculation!
                - In geometry, you can compute the minimum distance between a line and all given points - so, you can compute the closest obstacle point to your raycast, measure the distance it is from the line, and make sure it's at least "agentWidth/2"
        - Both of these algorithms are expensive when dealing with lots of obstacles/points; it might be fine for very small maps, but once you have more than a few obstacles you either need to get clever with what objects you're checking (e.g. quad trees to partition the screen, and only checking objects in the same quadrants where you're moving, OR you can use the other 2 ways:
            - The WHISKERS method is where we have some invisible point sensors sticking out of our agent, like ghostly whiskers; if the whisker intersects with something, the agent knows there's an obstacle there and it turns away from it until the whisker's in the clear again
                - "It's like a roomba, or a person who suddenly gets drunk if they're too close to a wall"
                    - This method tends to look a little wiggly, but you can smooth it if you tweak it enough
                    - There's a problem here, though: what if both (or ALL) of the whiskers are in obstacles? Well, it probably means the gap in the obstacle is too small to be traversed anyway; basically, if that happens, the agent tries to get back on the pathnode
                - This solution isn't seen too often, because the movement tends to be a little awkward, but it is reasonably performant
            - OBSTACLE PADDING, where we pretend there's a "force field" around the obstacle where the raycast will also hit
                - This way, if the raycast EVER gets through, we're guaranteed to be far enough away from any obstacles to make it

- Okay, so that's it for steering - but what about path networks?
    - So, if the agent can raycast to its destination, great - we can just use steering!
    - Otherwise, we need to "hop on the highway" and get on the path network by:
        1) Finding the nearest path node
        2) Finding the closest path node to our goal
        3) Search for the shortest path to the goal node
    - So, if we place the path nodes such that we can always see at least 1 path node, we can always get on the highway (even if it looks a little bit awkward, e.g. moving backwards to get on one of the path nodes)
        - Pros of this technique: can work with very few waypoints/extreme discretization of the search space (i.e. works with very small networks, leading to good performance); 2-tier local-continuous movement system (we still get a continuous steering movement system when we need it, which is great for FPS games!)
        - Cons: Getting on/off the network can seem clumsy (closest path node might be AWAY from the target destination), movement while on the network can be very predictable/robotic (this can be helped a bit with smoothing), VERY dependent on good path node placement (which requires either lots of manual work or a very well-tuned algorithm)

- ...and if you're homework will basically be all path node placement, let's talk about it
    - As we said, there's 2 big options:
        - Manually place all the path nodes by hand
            - This is surprisingly common - a lot of designers choose to do this to have more fine-tuned control over the player experience, trading development time for a better game
        - Automatically place the path nodes
            - This is a "design-time" AI; it's generated before the game is shipped and then saved, so we don't have to calculate it on the fly
                - These tend be slow - the algorithm we'll use in class is about O(n^4) - but they're still way faster than putting all the nodes in by hand
            - These tend to be especially common when dealing with large open-world style games with complicated maps
        
- A story before you go: the first Unreal Tournament had a map editor with an automatic path-node generator, but in the 2nd version of the editor they removed the button. Why? Because as the player maps got more and more complicated, their generator literally couldn't handle it - it would just start putting the nodes in random spots!
    - "...so, on Wednesday, we'll jump back in time to when games were cool and start trying to build this node generator for ourselves. See you then!"