#tiletype | Explore Tumblr posts and blogs

ahnmakes · 6 years ago

Text

devlog # 5 // hex tilemaps and pathfinding, part 4 (concept + integration of paths)

it’s the big day - we’re going to be implementing a pathfinding system, one way or another. this is going to be a long one.

to start with, not all pathfinding is equal – some pathfinding systems excel in certain areas and struggle in others. it might be helpful to reflect before starting on what kinds of pathfinding will be suited to the different use cases i have in mind.

so, what am i using pathfinding for in the first place?

well, mainly, i’ll need it for (a) highlighting regions where the character could possibly move, showing those predictions, and (b) locating an optimal path to a chosen tile.

in both cases, i’ll need the system to take into account different terrain costs (moving more slowly through water, mud) and heights (for example, a steep cliff face) that will limit how much the player can move in these regions.

i may also need to implement both two-layer levels (things with roofs, or where you can go under/inside) and high one-layer levels (things without any roof, but just dramatic changes in height) – this is not a primary concern, however, and i expect solutions will become more apparent as i understand my own implementation of the pathfinding.

okay, so, now that we understand what kinds of needs there are for this game, what kinds of pathfinding systems are available?

in this introduction to a* algorithms (what i’ll be merging with another tutorial to try to craft a system that matches our needs), we find a very insightful exploration of how pathfinding works.

the basics of each of the systems to follow is that we (as i understand it so far – you should read the tutorial, yourself, since it has really great visuals/graphs):

(1) make a “frontier” list, an expanding ring of tiles to be considered

(2) make a “visited” list that will keep track of tiles we have considered

(3) remove our starting tile from the frontier list, add it to the visited list, then add its neighbors/every touching tile that hasn’t been visited to the frontier list

(4) repeat step 3 for the next tile in the frontier list: remove it from the frontier, add it to visited, and add its neighbors to the frontier, recursively expanding the ring until we have filled all of the map area

this loop so far seems to be called “breadth first search”, an algorithm pattern that just expands and visits every tile.

we can sharpen these algorithms further if we implement code to:

(5) keep track of where we “came from” for each tile and

(6) set a target (early exit) – do a check when visiting tiles to see if that tile is the destination tile; if so, we can exit the loop and report back “came from” to construct a path between our origin and destination

(7) introduce movement costs, numbers we define (maybe 1 for plains/neutral terrain, but 2 for water and 3 for mud), and sort our next-to-be-checked/frontier list by priority of lowest cost (meaning we’ll look for the easiest paths before the harder, more expensive ones); at this point, the pattern is often called “dijkstra’s algorithm” or “uniform cost search” (this will always return the shortest path, but might be relatively slow to find it), OR

(7b) sort the frontier list by a priority of distance, choosing to check what’s closest to the target first; called “greedy best first search” (fast, but unfortunately, this doesn’t always return the shortest path – read the introduction to understand why)

and lastly, we can:

(8) combine both priority queues, sorting our frontier by comparing both movement costs AND closeness to the goal/final tile

with step 8, we construct something that is known as a* pathfinding – the most common and seemingly most competent choice for most pathfinding needs.

[image source here]

thus, returning to our needs, for (a) highlighting regions where the character could possibly move, showing those predictions, and (b) locating an optimal path to a chosen tile, a* seems like it can fulfill both roles. we might find it ideal to implement a simpler dijkstra’s algorithm for (a) in order for the pathfinding to be more performant (not as computationally demanding) – why?

because if we are showing highlighted regions for where characters can possibly move, we might choose to do so in realtime/by just hovering over a character. with this being updated so rapidly, it might save some performance to use a system that is doing less calculating. however, there are also other ways to approach this (such as only running the algorithm when the character is first hovered over, not constantly), so it’s just something to consider. most likely, we will only need to run pathfinding once or twice during a player’s movement phase, meaning the computational load should be minimal. let’s get something working and then we’ll optimise at a later point, considering ways to write more efficient code along the way!

oof that was a lot of technical info. let’s get into writing some actual code now. i’ll be following along with this excellent tutorial series and connecting quill’s implementation with the patterns and needs we’ve explored above.

lesgoooooooooooooooooo!

so, one of the first things i did was create a TileType class which keeps track of .. well, tile types. the types of terrain available in the game. this holds a name for the terrain type, a visual prefab of the hex (different colors, materials, etc), and – soon – things like movement cost; in the future, we can easily plug in different materials or different models that more fully represent the terrain.

in addition, i implemented random ranges for terrain types, right before instantiating (putting the hexes in the world), so that there would be variation in the tiles each time they are generated (in the future, i’ll likely do this with a sort of noise to create more artistic distribution).

this automatically creates a more interesting field of tiles. (i’ve also changed our player colors to not be clashing with the new tile colors)

two things pop into my mind here. first, it would be really nice to convert our tile types into enums somehow so that we can reference the terrain types by name OR number. secondly, i also notice that now, if we click to toggle on a hex (when no unit is selected), we will color them black and then white, erasing their original color. maybe we should be storing this information somewhere? this is something to do soon, but for now, let’s keep with the task of pathfinding.

the next major task was to build a graph of nodes (tiles), something which we will not see, visually, but which the computer will need in order to understand how all the hexes relate to each other - this is also why we set up to define which tiles are neighbors, i.e. adjacent / touching each other.

ran into a pretty tough bug when we started adding neighbors to node lists; it took me about 20 minutes to realise we hadn’t initialised the nodes before adding to them (so they were showing up null). this also happened because i am not completely understanding lists and custom classes (our nodes) and such yet, but i am excited that i knew enough about debugging and how to go through each line to identify what the problem was!

once this was sorted, this meant that (theoretically) we had a graph of nodes that contained all of our tilespace, and also were listing data for each tile’s neighbors - you can see an example of conditional/constraint code i used to identify where a neighbor should be.

from here, we are now able to move to the next steps of the pathfinding pattern: i create a list to hold frontier nodes and a list to hold nodes we have not yet explored. then, the big boy math.

i am not going to go through explaining each line, but i assure you that i followed the steps i listed above (again, you can find very complete information on this pattern in this a* introductory tutorial):

(1) make a “frontier” list, (2) make a “visited” list, (3) remove starting tile from frontier list, add it to visited, add its unvisited neighbors to the frontier, (4) repeat step 3 for the next tile in the frontier list, recursively expanding the ring, (5) keep track of where we “came from” for each tile, and (6) set a target; upon finding, exit the loop and report a reversed “came from” list to construct a path between our origin and destination

here’s some of how i implemented that scary math and logic code, for if you like to torture yourself :’) with so much thanks to quill and their amazing channel for making these maths more accessible.

now, once i had followed quill’s tutorial through these 6 steps, customising things as needed to align with how i had already implemented the rest of my assets/scripts, i was so thrilled to check out how our pathfinding looked!

after coding for hours and being entirely ready to enjoy the fruits of my labor, i immediately got a set of errors, the kind that won’t even let the program start. :(

at first this really shook me because i thought i had followed the tutorial pretty intently, so i felt it was likely something i had chosen to change in the process. and how would i ever find what it was, among hundreds of lines of code i barely understood? i had put in the “returned without route” debug message just for thoroughness’s sake, not at all expecting to ever see it. i felt immediately that this revealed what a fraud of a developer i am - that this was confirmation of exactly what i had feared for years, what kept me away from this project: that i was actually incompetent, not capable of this. a lot of hurtful self talk started right away.

and i checked that right away.

i remembered that this was just one of many things i had made across the years, and because i had chosen to trust myself along the way, i would not stop trusting myself now - every change i had put into the code had been purposeful, intentional, and i could rely on that it was doing what i had asked it to do. instead of remaining hurt, i would devote all of that frustration and disappointment and surprise to sorting this out, the same way i had with a million other projects. i explored the code for hours, placing debugs along the process to clarify exactly what was happening at each step, which things completed and which didn’t.. eventually (among numerous other debugging efforts), i put in a few lines to color a given tile’s neighbors cyan, to make it clear if all the neighbors were being calculated properly. and immediately, it was clear they weren’t – so back to the code where we define how to find neighbors.

if the neighbors aren’t being calculated properly, that’s surely something that would mess up pathfinding, right?

i went through each line of code and adjusted the logic until each of the tiles i clicked show accurate neighbors in cyan.

yay! well, not yet. the way i had implemented this looked accurate, visually, but the underlying code later showed that there were extra neighbors being calculated (and some still missing?) along the edges. after another tiny meltdown and taking the night to breathe, rest, i implemented code that would tell me exactly how many neighbors each tile was reporting. and because i didn’t understand the math’s logic fully, i decided to do what i did know how to do: count. i went through and, checking tile to tile, explored exactly what was leading to mistaken or missing neighbors. it turned out to be that i hadn’t appropriately accounted for the (1) edge tiles, where x == 0 or the y is max, putting the tile at the top of the map, and (2) alternating offsets depending on whether rows were even or odd, how each column of the map snakes back and forth (in other words, adding 1 to y sometimes means putting a hex on the top left, and sometimes it’s on the top right).

solved! actually, not yet.

back to the code! i went line by line, continuing to add Debug.Log reports at any major step of the process: what’s our destination tile? “destination tile is...”

did we send this tile and a pathfinding call? “path call sent to map!”

did the map receive it? “path initiated in map.”

what’s our source? our target ..? and so on.

each step through this process helped me understand much more deeply, as i began to feel i was really grasping how and why the code worked (or didn’t work). eventually, i thought: if the code is no longer showing any problems in logic, maybe there are typos? so, i compared my code to quill’s open source files from their website. scanning, scanning .. found something!

an issue in scope. i had defined certain methods within loops, where they needed to be outside - and some were outside when they needed to be inside. a few curly braces later..

B A D A B I N G

B A D A B O O M

“Path complete - sent to unit.”

it works, and it makes sense why it works!

this little black line seems so small, but it represents that the game understands how to navigate basic pathfinding through the hexes -- something i have dreamed of being able to do for years.

and with that, i am going to rest in the beautiful feeling which is trusting myself, knowing there’s no reason i can’t do exactly what i dream of - that the difference between “i don’t know how to” and “i very much know how to” is just whether i’ve devoted the time or not.

in the next devlog, i’ll work on implementing movement costs/further heuristics to make the pathfinding even smarter, then tidy everything up aaaaaand.. whatever else i feel like. until then, with love and certainty that i am indeed a developer,

ahn

#unity #unity3d #gamedev #game development #game design #indie #indiedev #indie development #indie developer #pathfinding #final fantasy tactics #hexes #turn-based

0 notes