I forgot which language this is in... I was going to say if it's C++ use pair instead of tuple, but then realized C++ doesn't have a Dictionary class.
C# actually, which I think is the least popular of all languages to write roguelikes. The frontend display plugin I use, Libtcod, has so little discussion or documentation on the C# version that this forum is the third or fourth Google result. There are probably simpler things I could use besides Tuples, but I just found them and thought it'd be cool.
Let's talk about pathfinding.
In a typical, that is
top-down, roguelike or almost any planar game where you don't have to worry about things like gravity, pathfinding is pretty simple. Just do an A* floodfill from Point A to Point B, or any of the performance improved alternatives if you'll accept an uglier path. This can become a noticeable problem with realtime games but not really anything made in the last 15 years unless you've got a huge number of calculations hitting a very complicated space.
Performance is not my worry, even though I do want to make a real-time game eventually. My problem is that A* fills are kinda useless for a platforming game, because the rules of movement are all different. With a top-down map, you only have to consider whether or not you want to walk on a particular coordinate. For me, consider a map like this:
Nomenclature: The ladder looking things are ladders, the thin platform looking things are platforms you can walk on or choose to drop through. I know this is complicated side-scroller stuff, try to keep up.
In this scenario, Point A can walk to Point B and vice versa, but getting from A to B is a lot faster if you're allowed to drop off a ledge. Getting from Point C to D also requires this, and it may or may not be possible for Point D to reach C depending on whether and how far D can jump. Point E has two major paths to reach Point D, but has to consider how far it wants to fall. And any part of this map can change due to the voxelized nature of the game.
I don't actually know how games with height mechanics do their pathfinding. You can look at games like Terraria or Starbound or 3D games like any Bethesda title and easily the confuse an AI trying to reach you. Stand on an unclimbable object and watch them dance and bounce below your feet. I suspect that most games take the easy route of just having the AI consider getting closer with the X-axis and leave the Z-axis to semi-random jumping. I can't recall any platformer-AI that can double-back and path around obstacles.
These are by no means difficult problems. There's an annual competition to write Java programs that can play Super Mario World in ways a human
would never conceive, although teaching an AI to follow pathing goals more complicated than "go right" does raise the bar a bit. I don't know exactly how these guys do their thing and while I'm curious, I've got something completely different in mind. And I think it'll prove useful with an engine that has to consider pathing in real-time. Behold (disco warning):
When the map generates, it group up every coordinate, and compares it to the coordinates around it. In then makes a list of "blocks" composed of contiguous cells with the same movement type; in this case, tiles you can walk on, tiles you can climb, and tiles you can drop from. Then it cycles through all the blocks to consider every other block: What blocks does this overlap with? What blocks can be dropped to? What blocks can be reached with different lengths of jumping? All of this information is stored as static Connections. With this precalculated map, when an actor has to get from Point A to Point B it doesn't have to consider every cell between the two all the time:
I am currently in Block 3, where is my target?
Target is in Block 5, does Block 3 overlap with Block 5?
No, what blocks does Block 3 connect to that can reach Block 5?
Do I have the movement types needed to cross those Connections?
How many cells will each path take me?
And so on. That way, each AI is only flood-filling a small one-dimension-ish portion of the map at a time. This also means that whenever a tile in the map changed, only a small portion of the map has to be updated. The player could certainly spoof this with a bunch of adjacent ladders or weird jumping windows, but it's an idea I'd like to pursue.
So, that's what I'm working on now. If nobody hears from me in a while, send help, I'll probably be very hungry.
Author
Topic: Aqizzar makes a game (Read 15465 times)