NathanLovato
commented
5 years ago Note for pathfinding: I'm looking to use a Tilemap to handle static colliders. @razcore-art already coded a decoupled system for his remake of OpenRPG. See this file and branch: https://github.com/razcore-art/godot-open-rpg/blob/rebuild/OpenRPG/src/Board/PathFinder.gd
It separates characters, a pathfinding node, and a game board. He also wrote functions to make Astar work in 2d, which is more convenient than the current built-in implementation, that's a bit abstract and 3d only.
Razoric480
Initial proposal by @Razoric480
The AI system is split between 3 facilities, plus a scheduling utility, depending on project and AI complexity:
Decision making
You've already covered in part with the State machine in the previous course. I don't think it'd really need to be that much more complex for a Metroidvania style enemy - WATCH, ATTACK, FLEE. Though a behaviour tree could be a fun alternative for more complex creatures. Either way, the purpose of the actionable end-node of such a tree would just be to set the appropriate flags in motion for the Steering behaviours. Implementation: In godot, that'd be a tree of decision making nodes - either a state machine holding a few states, or a behaviour tree holding its parameterized branches and actionable leaves.
Pathfinding
Depends on the terrain, and how smart the enemies have to be. Given they're in the air, frequently that might mean 'no pathfinding', but if they're going to head around corners, then yeah, you'd need something. A star is the the classic solution. Split your level into a graph and run a heuristic driven path through it. You can also go for a hierarchical a star if you expect the AI to do some very large sweeping paths from one end of the map to the other (this is where you have multiple levels, top, more coarse level representations, and more granular levels below. For example, top level is a bunch of interconnected cities, with the level below that being the inside of the city, and the level below that being inside individual buildings.) Heatmap as you've called it, or a repulsion/attraction, field flow, etc. I've seen it with quite a few names. Your gameworld is split into a grid, and each of the cells contains a vector pointing to where an entity has to go to reach the goal. The only issue with it is that it doesn't really scale all that well when the 'target' direction is a player, because the field has to be recalculated when they move. Though this can be mitigated by having the target be the 'area' the player is in, and the AI is then expected to move in a straight line once they get there - then you only recalculate when they change rooms. Or, if we're diving into C++ and threads, we can probably afford to recalculate it on the fly, depending on the complexity of any given environment. The big advantage is that all an entity needs to do to pathfind is to check which cell they're in and request the direction they should be moving. Then you can have thousands of entities move extremely cheaply - a swarm of locusts, or pathfinding particles. Nothing stops you from having multiple pathfinding systems, then again, based on the entity's needs and complexity. Implementation: In Godot, they'd both live as an over-node that has access to level data.
Steering
This is where the actual action is calculated, and is the most modular part. The behaviour is passed the information it's going to need (the actor it belongs to, its direction, acceleration, position, the target position, acceleration, etc), it does some math, and out pops a linear vector and an angular rotation - this is where the entity feels it has to go and/or turn. The actual movement code takes that vector and does the actual movement. You can then have an inherited system with a common 'calculate' method, and you can prioritize (move away from imminent obstacle) and/or blend them together (a Pursue behaviour AND a turn-towards-target behaviour.) Implementation: In Godot, that'd also be a tree of nodes, next to the decision making tree.
Could have an AI scene for each AI types that contains decision making and steering trees, and just re-use it for every enemy of that type. Godot is nice like that.
Scheduling
AI can get expensive. The bigger the levels, the bigger the maps, the more cells, targets, behaviours, and entities you have, the longer the whole thing can take. Threading can help, for sure, but another solution is to only iterate over how many entities you've got the time budget for. Instead of just iterating over each entity, you create a job that maintains a state until it's done. You tell it to run for a maximum of 1, 2, 6 milliseconds, and when its time is up, if it isn't done, it puts a bookmark where it left off, and next frame, it'll resume until it's done or it runs out of time again. Until an entity has had its recalculation completed, it can use its last result.