Day 6 and 7

Day 6 was mostly a wash in terms of actual progress. I dove HARD into pathfinding. I've always been interested in various high-end pathfinding algorithms but never actually taken the time to implement most of them. 

I started off with using the FloodMap system that came as an example in the RetroBlit framework, part of the RetroDungeoneer demo. This is know as a Dijkstra map in the rogue-like world. I really love the concept! A map that has a path from every point to a set of points? Great! The problem is.. even on my 'small' map of 128 tiles by 128 tiles it was slow. Creating a floodmap took a pretty constant 12ms if it only looked at the tilemap, and up to 30ms if it also looked at entities on the tiles. I'm quite sure I could speed that up... but unless I got it 10x faster I would be seriously limited on how many 'paths' I could create in a reasonable time. I decided to try other things before spending more time with it though.

I spent at least half an hour reading a paper on Near Optimal Hierarchal Pathfinding. It was very interesting stuff, but before I put a lot of time into it I took a quick look at the source code. Sadly, I simply couldn't bring myself to use a pathfinding algorithm that had an order of magnitude more code than my whole project so far. My interest then shifted over to Cooperative Pathfinding. This was super interesting to me since it is a variation on A-star that adds a temporal dimension to it so units can share information and pathing. However, the paper was not a quick read and reasoning in a temporal space after just moving on from HPA was not working for me. I needed something simpler, and reluctantly decided to just implement a super dirty breadth first search with an early out. This is essentially Uniform-Cost-Search.

Tragedy! My algorithm was simple and should have worked, but the generated path was really bad. After spending almost an entire hour debugging and putting in the ability to visualize the algorithm step-by-step... I was still no closer to a solution. Eventually I binned the whole thing and just wrote the a-star algorithm I already knew how to do.

Like I said, Day 6 was a wash and it took me all of it just playing with different pathfinding systems. The start of day 7 was writing the a-star code and testing it. That's what is in the current version. Click an entity and then click a spot to give it a destination. Hold spacebar to see the generated path. Simple testing shows that 'close' paths take 0 to 2 milliseconds, while the worst case corner to corner takes about 27 milliseconds.  Not great, but I can work with it. I needed a good best-case and can work around the worst-case.

Just so I had something different I decided to re-do the buildings. Previously I was waffling on if they should be multi-tile or single. Single it is! With that decision they really started to resemble entities; So I made them inherit from Entity. This of course makes for one really hilarious point.... You can select them, which is great! But you can also move them. Woops! I'll fix that for next time and actually start making buildings DO something. Besides moving that is.