So… I crammed through the Realm Rush videos today, until I got to Explore_Thy_Neighbor. Then my wife decided it was time to watch olympics, and that I was more than welcome to keep programming, but NO MORE VIDEOS.
So Ben went through the basics of Breadth First Search, and the idea for the algorythm was floating through my head since that discussion, so once we had a starting point, I went ahead and finished it.
I didn’t run through the visualization of the search algorythm, as I wanted to focus specifically on substituting the Enemy’s path with the results… But I also figured that there was a good chance that there would be more than one enemy, and they probably wouldn’t be starting on startPoint…
So first, I wrote the ExploreWorld… I made it a function that returned a Dictionary<Vector2Int, Waypoint>. I fed it a startpoint, and nothing more…
To that, I added a List queue…
So… starting by adding the starting Waypoint to the queue, the next step was a While (queue.Count>0)
Using each Waypoint in the queue… Check the waypoints in each cardinal direction… if you find a waypoint and it’s NOT in the new Dictionary, add it, but instead of the waypoint you just found, put the Waypoint you’re testing from in the queue. Add the new Waypoint to the Queue. If you didn’t find any waypoints, nothing is added to the queue, and every waypoint is guaranteed to only be tested once because you check it against your resulting Dictionary.
So… that’s handy… you have a Dictionary of points… and from any given point, if you follow the breadcrumbs, you get back to your start position…
The next function returns a list of waypoints… it’s actually the function I call, as it calls the Explore world function… It checks the dictionary for Endpoint, and inserts each waypoint into the list.
So then the Enemy calls that function, passing the enemies location instead of Startpoint… the result is a list, much like the one we started with. Then you just call your follow path routine and go home.
It worked great… until I added extra enemies… some of the time, those extra enemies would walk over each other… it would seem to me that two capsules shouldn’t occupy the same space… We can’t have that…
So I added a public field to Waypoint called “containsObject”… Whenever an enemy moves, it marks that space it just moved into as occupied… so if another enemy tries to enter that space, it calculates a new path. I also changed the ExploreWorld to ignore tiles that are occupied.
It took some trial and error (and lots of figuring out how to break out of a coroutine when the enemy’s blocked), but here’s a video of the result so far.
I’ve noticed a few anomolies… like if a path is recalculated with a spot blocked it ignores that spot until it needs to recalculate… The solution might be to force a recalculation every few moves no matter what,. I’m not sure yet. Another solution may be to wait a cycle and try the move again, only recalculating after 2 or 3 blocked moves.
The blocking mechanism I used also makes it so that it’s possible to have no clear path to the end point… It’s programmed to try again in one “movement cycle” if it can’t find a path, and right now choke points can make that quite possible.
Now to watch the rest of the lecture to see Ben’s solution.