Jump to content

  • Log In with Google      Sign In   
  • Create Account





Pathfinding

Posted by JTippetts, 13 November 2013 · 500 views

Goblinson Crusoe Urho3D pathfinding turn-based rpg hex-based rpg
Now that I've started fleshing out the combat AI in earnest, things are starting to get a little bit trickier. AI is one of those fields that is pretty nebulous and highly domain specific. One of the tricky parts of what I'm facing now is pathfinding.

Pathfinding is superficially easy. It is not difficult to get a basic A* algorithm up and working. There is drop-in code all over the internet, and the algorithm itself really isn't all that difficult to grok. However, where it can get tricky is in what I think of as situational pathfinding. Consider GC. He can now build barricades, which brings the tactical considerations of pathfinding up a notch. You see, barricades block so that you, the poor AI-driven mob that must defeat GC, can't move through a tile. That means that if you use a basic pathfinder, you're going to go around the barricade rather than attempt to go through it, because the barricade is blocking. What if GC surrounds himself with barricades? Then you're stymied. All you can do is stand there like an idiot because no valid paths present themselves. However, barricades are destructible. You should be able to bash your way through one, with a little bit of determination and good, old-fashioned elbow grease.

So, what if you modified your pather so that instead of just considering the blocked/unblocked status of a tile, you considered whether or not it was destructible as well? Then, you could ignore tiles that have a barricade when generating the path, then as you follow the path and encounter destructibles, you can knock them down on your way to total GC obliteration. Of course, if you just brainlessly ignore destructibles, then you end up with paths that choose the shortest path through the full blockers, and if that shortest path passes through a single, isolated barricade you end up attacking that barricade when the "smart" thing to do would be to go around it. You just wasted seventeen turns beating down a barricade that GC dropped on his mad dash to safety. Well done. Here's a medal.

So then you have to modify the pathfinder some more. Instead of just ignoring destructibles, you assign them a path cost that is higher than non-blocked terrain. But then you have to calculate the cost, and that gets tricky again. Done properly, the path cost to pass through a tile holding a destructible needs to equate to the cost to a mob for destroying it and passing through. The simpler means is to just use the health of the barricade versus the rate at which you can deal damage, to estimate about how many turns it'll take to knock it down. More complicated means will also have to take into account resources you spend to do so, such as energy or consumables used to cast the spells or perform the attacks to destroy the barricade.

Of course, you also might want to exclude certain classes of destructible objects from consideration. That destructible that you just marked for death might be a barricade, or it might be your cousin Grok. You see, in GC anything that is destructible has a CombatStats component, to encapsulate life, attack powers and resistances, etc... So having a CombatStats is a good indicator of whether something is destructible or not, and is probably what you will use to make that decision. But you can't just blindly consider all destructibles as potential obstacles to eliminate on your way to full GC extermination. Because it just might happen that you are presented with two possible paths: through a barricade with 1000 life and -100 Physical absorption, or through a squishy little thing with a +15 Fire vulnerability and a Physical def that even a mouse wouldn't envy. Your pather will weight the heck out of that squishy thing, and it's probably going to be picked, and that means it's curtains for poor, flammable, punchable Grok.

So now you have to do a faction check against all destructibles. If it's Grok, and he's on your side now because you forgave him for eating your Roasted Goblin Flank, then you probably shouldn't bash your way through him on the way to complete GC annihilation. That means excluding anything from your faction. But what if you are an evil, ambitious bastard, and while Grok isn't exactly an obstacle to your path of world domination, he could later prove inconvenient? Then maybe you should weight towards eliminating him, at least a little bit.

But wait! Some destructibles are also lootables! So maybe that thing in your way can be looted instead of knocked down, with the added bonus of obtaining some possibly-precious resources. So now you probably want to assign a lower cost to that tile, to make any path through it look more attractive. But how much more attractive? Well, what resources are you low on? What resources do you make use of? How valuable is the resource in question to you, personally? If it's just a tree, well, those are all over the place and you probably already have more wood and leaves than you know what to do with. But maybe that resource node is an obsidium vein. Wow, wouldn't that be neat? Obsidium! Why, with that obsidium, think of the spells you could cast! GC will rue the day he set foot on your island! And it's not that far out of your way, either, so you don't even really have to change your plan.

But just hold on a second, here! Why, you don't have to put yourself directly next to GC to attack him after all! Didn't you just figure that there is some obsidium you can gather along the way? And can't you cast a pretty hefty Earth Sledge spell with it? Why, with Earth Sledge you can wipe out GC from 4 hexes away. Suddenly, you don't need to get through that barricade after all! Just make a slight adjustment to your path goal to find a hex that is within 4 of GC and that passes through the obsidium node, and boom! Earth Sledge to the face!

So what was once simple (A* pathfinding using a distance heuristic) has now become complicated as shit. Now you have so many other factors to consider when calculating a path. Still, some of this is a bit of a red herring. For instance, you could separate out resource collection into a different phase of AI, and if your unit is not currently interested in collecting, have it disregard resource nodes, or consider them for destruction. (Be careful with that one, too, btw; it can cause the player heartbreak or hilarity if he/she sees a mob knock down a valuable obsidium node just because it's not currently interested in obsidium.) You can set some reasonable restrictions on decision making. For example, in the middle of path calculation is not the time to suddenly decide to switch to casting Earth Sledge from 4 hexes away. That should have been decided in an earlier phase.

This is the quagmire I'm currently wading through. It's requiring a pretty significant overhaul of the pathing system, in order to incorporate more comprehensive heuristic calculation. This is one of those "danger points" in the process for me, when I'm facing a complicated and messy problem which doesn't really provide pretty, screenshot-able results at the end, but which kind of has to be done in order to advance much further on the AI side of things.




What libs have you looked at using to do pathfinding if any? Curious to hear your thoughts and experiences with them...

No libs, at least for this. (I've used Detour/Recast in the past, but it's not appropriate for the tile-by-tile movement I'm using here.) Like I said, the basic algorithm isn't really all that difficult, and you can get the framework done fairly quickly. The tricky part is the heuristic calculation, and I've always found that to be pretty domain-specific, due to how it has to intertwine with game mechanics.

PARTNERS