After finishing a bunch of menus, all in-game management needed for the locations are done, and you can collect and use items, equipment and books (to teach new skills to followers). I then devised an algorithm to place items in locations - at first I was just going to scatter items around randomly, but then I noticed that many items placed were not actually accessible (they were surrounded by obstacles, like trees)! Not only did this mess up the balancing of items in the location (as any number of the placed items could be inaccessible), but it was also very taunting to have items in sight that you couldn't reach. The random algorithm could also be slow because it would have to test a bunch of random locations before it found one where an item could be placed.
To solve this, I decided to add all accessible locations to a queue, and then pop locations from the queue randomly to place the items. Since the queue only has usable locations and locations are only added once, this guarantees that I'll get a valid and accessible item location every time I remove a location from the queue. The queue was created using a flood-fill algorithm, where from the start position, it would add all adjacent locations that weren't blocked. Like using the fill tool in paint, this only adds locations that could be reached from the start, and entire sections can be cordoned off by obstacles in bottlenecks.
This brought me to my next issue - while I hadn't realized it before, sometimes the majority of the locations were inaccessible! From the location generation algorithm, the path is guaranteed to be accessible, but if obstacles hug the path closely, the rest of the tiles could be cordoned off, eliminating the possibility for "bushwhacking" and having as little as 3,000 of 65,536 tiles available! This caused me to adjust the generation algorithms by adding "invisible" paths to increase the number of accessible tiles. And in the worst case if less than 10,000 accessible tiles are located, then it will completely regenerate the map (this is expensive, but rare).
Finally, I wanted to add chests for special (and unique) items and pools which would recover follower health. The problem with these is that they are permanent events, and they - like obstacles, can cordon off sections of the location that I thought were accessible! An apple can be picked up and disappear from the location, but a chest is only opened and remains blocking paths where it stands. I had to ensure in the chest placement algorithm that they could not block any possible paths of their neighbors. For the most valuable items, I decided to make some of the chests "trapped" as well, starting a battle before it lets you get the item. You can run, but doing so will cause you to lose the item, and you can never get it back!
With all of this done, everything is complete for the generation and gameplay of locations. As shown in the video above, you can move around, learn skills, manage followers and items - everything that will be in the final game except leaving the location to return to the world map. There are still some loose edges and balancing needed to be done, but once I finish that, the world map (and necessary menus) and two cutscenes, part one (and the demo) will be complete! I am really hoping to have the demo done in time for submitting to the IGF, so look forward to that and future updates! Also, anyone who wishes to help test and balance part one of the game, definitely send me a message, as I should be ready for that in the next week or two.
