4 ms·
> The paths are simplified to produce fewer nodes with gentler turns between them, which is helpful when units drive along them It looks like a much more usefu
by otikik 4y ago
> The paths are simplified to produce fewer nodes with gentler turns between them, which is helpful when units drive along them
It looks like a much more useful optimization would be to produce a simplified map that splits the "real" map into "connected regions" via chokepoints. Pathing on that simplified map should be orders of magnitude simpler than on the "real" one. That's the "high-level plan": go to region A, then to region B, then target is on region C.
Once you have a high-level plan, each unit only need to do the expensive pathing until their next chokepoint (or to the target, if they are on the same region).
This is especially relevant on dynamic maps that are continuously changing (e.g. enemy units blocking paths, or building structures, or fog-of-war that keeps being updated, or closing and opening doors). Re-calculating the high-level path every time for every unit, and throwing it away when there's a change, is too expensive. Much more economical to recalculate the high-level map once for everyone, and then do high-level plans + pathing to the next choke.
Rimworld has a video where they explained their Region system, which implements this: https://www.youtube.com/watch?v=RMBQn_sg7DA https://www.youtube.com/watch?v=RMBQn_sg7DA
- Agentlien 4y agoI've implemented similar systems for commercial games I worked on and it works really well in a lot of fairly tricky situations.
- hinkley 4y agoHalo 2 devs also bragged publicly about how some of the AI is compiled into the map. The map understands things like “cover” and the enemies will seek out that information when reacting to the player, rather than evaluating the environment for themselves. The map in Rimworld is destructible though, so that sort of technique doesn’t quite work.
- bee_rider 4y agoI really liked it the Halo2 AI, it was sort of the high water mark in FPS AI as far as I saw. I probably just haven’t played whatever games are advancing it; I heard the FEAR series had especially good AI but I only played it a little bit. One thing I really liked was how chatty the enemies were. I think they claimed the Grunts would “act smarter” when Elites were around to command them. No idea if that was just marketing fluff though. Hard to notice either way, because there’s the confounding factor that the Elites are just stronger enemies so those fights would naturally be harder. I’ve always thought it would be cool if the developers would take a “no cheating” approach — model what every unit has observed and require them to make a noise in order to share that information. It would add another dimension of difficulty — “highly trained” units could be modeled as able to communicate more information with less noise (and then add some units that just use hand signals or if it is sci-fi, psychics that can give orders silently).
- mlsu 4y agoI never played FEAR, but ended up reading basically this whole page when it was posted here a while ago: https://alumni.media.mit.edu/~jorkin/goap.html https://alumni.media.mit.edu/~jorkin/goap.html Really interesting stuff. It appears chronologically dated at this point, but I'm not sure that anyone's made substantial improvements, given the lack of investment into single player games.
- _carbyau_ 4y agoPlayed FEAR and the sequel coop with a friend twice - once as each char. The AI is still amongst the best I've come across. Division 2 did alright but no better. If I was trying to do AI for a game, I would suck down every link on that web page. Even if you think you can do better, this is a great bar to measure against.
- ilyt 4y ago> The map in Rimworld is destructible though, so that sort of technique doesn’t quite work. It could just be updated. Terrain/building destruction events don't happen all that often in Rimworld, maps also aren't too big
- meheleventyone 4y agoRimworld also has to update the pathing and information for all the buildings and usable by NPCs 'stuff' so is likely doing a lot of this already.
- hinkley 4y agoRunning calculations are one thing, but for Halo 2 it was done at build time.
- ilyt 4y agoWell, if you can precalculate it, zero reasons not to. You could possibly also do it to somewhat destructible map, just recompute the area where destruction might happen and swap that part when destruction happens in game
- EamonnMR 4y agoThis is what they did for the StarCraft pathfinding, but I can't back that up with the links I wanted to send. Also, StarCraft definitely uses the static map for long paths, units will get stuck if you block choke points with mobile units.
- BlueTemplar 4y agoYet another example (with nice animations, and discussion about how to deal with non-contiguously pathable regions) : Factorio Friday Facts #317 - New pathfinding algorithm : https://factorio.com/blog/post/fff-317 https://factorio.com/blog/post/fff-317
- otikik 4y agoThat was really interesting, thank you. Using the low level map for the heuristic on the high level one is neat. Making the high level algo resumable is also very neat. I still think they should be pathing “only to the next region” on the high level map.