Working with Hexes, Dijkstra's algorithm?

Unity Courses Talk
, ,
#1

Turns out I had the same ideas as @Brian_Trotter to convert this whole system into a hex-based system. (I think hexes provide more interesting gameplay)
It took a little figuring out to get the grid snapping to work, but as far as the directional searching is concerned, it’s just as simple as quads. I currently have two versions of everything in the scene, (HexWaypoint script and a Waypoint script, for eg.) and it’s all working.
Last night I wasn’t able to fall asleep and my brain kept thinking about pathfinding systems. I came up with a way to do Breadth First Search, as well as potentially a way to make a system that works similar to Dijkstra’s in terms of having movement costs. I have yet to try it, but here’s the theory as best as I can explain it:

StartWaypoint explores everywhere around it, the nodes it searches remember who found them.
They continue searching, ignoring places already labeled as having been searched, and labeling places they find with their own name. Once the end is found, each node simply has to remember who found it to create a path back to start.
To add movement costs (Theoretically, this might not work), I would add an Int variable to the node defining it’s movement cost (0 for normal ground, going up as it gets more difficult). When that node is searched, it starts a timer that ticks down by that variable. When that timer reaches zero that node will search other nodes. This will lead to the pathfinding taking longer to explore places with higher movement cost. Again, I have yet to implement this, but I THINK it will work. Please correct me if I’m wrong.

#2

That would work, but it would involve actually delaying the search as well, and enough that the average user might notice. That’s why I had to go with a PriorityQueue… In my case, I wrote a generic PriorityQueue that behaves like a list, but that was just for the excersise of doing it…

Create a wrapper class with a float and a waypoint, and then use a list of this wrapper class as your “queue”. When you want to add a tile to the queue, calculate it’s turn counter (the current turn counter + movement cost) and then search the list and insert the wrapper just before the first element with a higher float). This keeps the list ordered by total movement cost from the center. As you search the next tile, simply remove it from the list. The float in the wrapper becomes your new turn counter.

#3

That makes sense. Thanks! Now to see if I can implement it… :stuck_out_tongue:

#4

I think it’s defeated me. :stuck_out_tongue: I’m moving on with the rest of the course.

Privacy & Terms