This week felt fairly productive. I spent some time trying to figure out this pathfinding, and managed to simplify it significantly in the end, I created a small feature that I think will be vital in AR, and managed to get the player actually moving.
I started with pathfinding. At first, I spent a while trying to make a good implementation of Dijkstra’s algorithm – trying to find the shortest path to each tile that could potentially be reachable. What this led to was a lot of infinite loops and freezing Unity. I even delved back into my EECS 281 (Data Structures & Algorithms) projects to try and get a feel for how to approach pathfinding in a good way, as that was the only time I’ve really done pathfinding.
Eventually, I had an idea that seemed promising – I could find every tile in range, raycast from each tile to the start, and using that smaller subset of tiles in between the start and end to pathfind. Then, if there were obstructions or anything else, I could A* from the point of obstruction to the point on the other side!
…Thankfully, that thought process made me realize how much I was overthinking things. I don’t need to find the shortest path between each point – just a path from start to finish, and I can purge any path once it gets too long. I think I actually started with that thought process, but iSo I instead would just grow outward, highlighting points as I go, and if the path got too long, the point would be ignored.
The algorithm went from this:
Note how much smaller the text is in the old function. Also, one should note that the large blocks in the new function are simple conditionals checking all adjacent tiles. I also feel obligated to make a joke about/comparison to Pathfinder vs. D&D 5e here: my old code is like Pathfinder, the new code is like 5e.
Implementing and debugging this still took time – there were a fair few weird interactions and edge cases to take into account, but ultimately I got this:
Compare that to the image of what it’s supposed to look like from last week’s blog post:
Additionally, it works with rough terrain! In this image, the red tiles are rough terrain:
And here is how the character would be able to move:
I’ve hidden tiles in the game view, as once I transition back to working in AR next week I won’t want the tiles to obscure the map. The perspective is a little bit off between the images, but the two red tiles on the right in the first image are the same two red tiles in the bottom right of the third image. I specifically placed those there because they would cost two tiles of movement to reach as rough terrain, but would be the limit of the player’s movement in normal terrain. As for why the player is still able to reach the edges on the left side, the player can move diagonally between them without technically touching rough terrain. I don’t currently have solid obstructions at the moment, but I am not concerned about ease implementation – worst case, if I made the cost of traversing an obstruction something like ‘999,’ it would be trivial to implement, if not clean.
My plan had originally been to work on networking after that, but after pathfinding that seemed like a daunting dive. Instead, I decided I needed to get the player to actually move first. This was a little more difficult than I had anticipated, as my Touch Management is definitely not as good as I would like, but I had it working sufficiently in only a couple of hours. Now, when you tap and hold on a character, after a brief moment (a sanity check for accidentally tapping on the player), they will move to wherever you drag, and then snap back onto the grid when you release. From there, you can pathfind as normal. Due to the fluid nature of D&D, I did not lock this to tiles that the player “can” move to, as a DM might rule something different. Here is player movement in action:
Picture-In-Picture, for AR
To go with this, I also added another feature that I suspect will be vital to the AR implementation: a picture-in-picture minimap-type-thing for dragging. Due to the fact that a player will likely frequently be sitting at off-angles and at a large distance from the game, I realized that just scaling tile collisions won’t be enough, so I created a Picture-In-Picture that shows an orthogonal top-down view of where exactly the player is dragging on the grid:
While it is a little choppy here, I’ve found it to be extremely useful for trying to precisely select a tile. I’m very happy with how this turned out, and it ultimately has cost me very little for a whole new feature thus far. Moving forward with this, I would like to be able to have labels for each tile that have a chess-like name that only show up in the PiP – something like A1, etc, and I’d like it to rotate with the player, but those are not high-priority tasks. It can be confusing now, so at some point I will have to fix that, but I have ideas.
After that, I started running through a tutorial on setting up the PUN – Proton Unity Networking – library and getting networking running. I was able to connect my personal phone as well as a Pixel 2 I received on loan from a contact in a basic game (though I couldn’t actually do anything as the sample game was not designed for touch screens), and have started working through a tutorial for it, but haven’t made significant progress yet.
Ultimately, I’m happy with my progress for this week! I got through a problem that I knew I would struggle with fairly unscathed, got another function that was harder than expected working well enough, and implemented another function that I suspect will be important surprisingly easily! For next week, I will work more on Networking, and I will also get back to my AR implementation. For now, my plan is to use a ground plane for the map and I will just do more testing on the Pixel 2, which I was given specifically to take advantage of ARCore.