visionvortex.de

Performance optimization is a big thing for procedural content creation. You don't want to wait like forever for the level to load. So, since the last blog entry I did some groundwork for getting the framework do it's thing faster. This week, I took a VERY close look on the generation modules, the walkers. A walker is basically a Sampler/Placer for grid values with a specific algorithm. Each walker does something else. Some Walkers have a very low performance footprint. They complete in under 4 mas even with map sizes of a 1000 square. Which means one million cells. One bloody million. Needless to state, that some other walkers are WAY more expensive when it comes to them doing their thing. Like the Mazer. This walker creates mazes. Ranging from perfect mazes to variations with loops and such. And even with small maps, this comes with a price. its like 300ms average for 50 square grids. But that's only after my first optimization pass.

The whole dive into performance optimization got me thinking a lot. About how to approach programming and about how to approach certain problems from the start. I really learned a whole lot already, but I think I just scratched the surface there. Nonetheless, with the Mazer I thought, what makes an algorithm like this take a long time to complete. Looking at what the code did, I realized, it's the number of samples that you take and HOW you take them. So restructuring internals to have as few sampling steps as possible did a lot for the performance. Another thing that hits heavy on the sped side of things, is checks. Every time you ask if, it takes a little while. Things sum up. So, going through the code and removing checks wherever possible also seemed to do the trick. It also made the code a lot cleaner. So that's something that did't hurt in that compartment, at least.

In the last week, I tackled every walker like this and tried to get things running faster. One thing that did cost a lot of time though, was the process in which the generator evaluated it's chain of walkers. When I started off with PMap, I thought it would be cool to have step by step debugging. Well, it actually was cool, for development. But with things up and running, I noticed that I never really used that feature again. Internally that mechanism was like:

Generator: "Hey, active Walker, take a step."
Walker: "All right man, no hurry! Already stepping forward... OK, done!"
Generator: "Awesome! I'm fine with that. Take another step."

Walker: "Wait, what? Why, you know that I could have run..."
Generator: "Just another step, OK? We don't need to discuss that."

The three lines at the top sum up how things run internally. In between the I'm ready stepping and the step again command, the generator would check back with the controller if Manual Step Mode (Debug mode) was active and the controller would then trigger another advance. Allright... I thought to myself. And that with a million steps. Awesome. You know, with art and game development I often heard the term "kill your own babies". Which doesn't mean "make a vicious bloodbath" but rather: "Sometimes it's necessary to say goodbye to some things you loved. Scrap them and try again. More often than not, something better will emerge. So I started killing of features that I didn't use or that weren't fully implemented. That, again, made the code cleaner, more readable and increased overall performance.

I'm quite happy how all that turned out although I think, there's some potential left for optimization on one Walker or the other. I decided to move on for the time being and return to those special cases later. Performance was OK. Not stellar, but OK. The special cases I'm talking about are the ConnectivityCarver and the Mazer btw. There is a lot of potential for optimization left and the optimization is needed direly. But I need to get a few other features out of the door before prepping for release. And part of those were three new walkers.

At least that's what I planned on doing. But it gnawed on me. I lay awake at night and thought about how to get things done even faster. And I had some Ideas. Starting off into this week I just had to try this out, just to get it out of my head. And It worked. Oh boy, and how it worked. To give you some numbers. On a 50x50 unit map the Mazer would take around 1100 ms to process the map. That's around 2500 cells. That was way to high. After optimizing again, i'm down to values arounf 5 - 24ms, depending on configuration. That is awesome. About 60 times faster on average. Wow. I was blown away. How did it happen? Basically I realized that modifying Lists and looking things up in lists can be very expensive, at least with large lists. So to boil things down and not bore you to death... this what it boild down to:

  • Try to remove things from THE END of a list wherever possible. (That is the cheapest operation).
  • Instead of picking a random member from the list, shuffle the list once and then process it from the end.
  • If I need randomization and discard list members for not being suitable, randomize again ONCE after the next successful placement. Nobody will notice if I randomize after declaring a cell for not being suitable.
  • Randomize as few times as possible.
  • Use bit-wise math wherever suitable.

The Debug output for the mazer looks like this after optimizing:

PMap Schreenshot 1
Proccessing times for the Mazer Walker

The SnippetStamper uses ScriptableObjects called PMapRoomSnippets. Those are essentially pre designed rooms that can be stamped onto the map with a SnippetStamper. That's cool if you are designing dungeons, or want to add special boss rooms or whatever. Good news, I's done! And it's also rather fast. I also added the DoorFinder. This one adds a vale at a positon where a door is likely and also has the option to allow random placement of doors in corridors. The results are fast and nice. The last (probably) Walker I will complete before release is one that's called Value Placer. This one is a bit tricky to explain, so I think I'll do a complete devblog entry on this one.

So, what's left on my Roadmap:

  • Performance Optimization Main Pass
  • Performance Optimization Walkers
  • Redesign Walker chain evaluation system
  • Snippet Stamper
  • Door Finder
  • Performance Optimization Walkers Part 2
  • Value Placer
  • New DataVisualizer (Support for very large grids)
  • Bugfixes
  • Class Documentation
  • Create Manual
  • Create Tutorial Videos
  • Release

Now that'S manageable, I think. In the meantime, let me know on Twitter or below what map sizes you'd be using for your games and overall, what features you would expect. So I'll leave you with a small animation of some different maptypes PMap can produce with a Mazer, Or a Snippet-Stamper / Connectivity Carver / Door Finder setup. So long, stay awesome!

PMap Schreenshot 1
Some Map Types for PMap

Back to Top

(c) visionvortex.de 2017