posted by
Unknown |
06 October 2020Trying to solve NP-hard problems in realtime is not a good idea
Legendary Orbit Golf (https://ldjam.com/events/ludum-dare/47/legendary-orbit-golf) procedurally generates a small universe, which is a field of planets. In order to not look over clean and make the paths between the start and the destination hard enough to be interesting, we didn't want just spawn them into a fixed grid (quad or hexagon grids come to mind). Instead they should be spaced unevenly and the planets with various sizes should try to pack close together while never overlapping. This problem is commonly referred to circle packing, specially circle packing with different circle sizes. Unfortunately this problem is NP hard and kinda time consuming to find good solutions. The original game idea included a infinite universes, so that you can shot into any direction are guaranteed to eventually hit a planet. We cycled through a various approximation approaches to get a stable planet layout in a reasonable time, the final solution is fairly simple, but is unable to execute continuously, because it is too slow. So we are now just generating one finite universe on startup and that it. Trying various approximation approaches and trying to integrate them and debugging problems around it probably took 2 people over half a day of time.
Celestial mechanics are kinda complicated
The game is basically a gravity physics simulation. But instead of being perfectly realistic, we are making a game, so we have to bend physics. So a general n-body simulation would not fit the intended game play, as this would be to hard for the player to easily chose stable trajectories and for the game it would be too hard to procedurally generate a "fun to play" planet constellation in a reasonable time. Hardcoding a universe would take too much time too.
So we ended up doing simple 1-body simulations, considering the masses of planets and the spaceship vastly different, make the ship insignificant. Planets do not interact with each other gravitationally, they have a gravity well defined by a simple radius and these radi do not overlap, so the ship is only ever being affected by one planet, making a log of game logic and gameplay a lot simpler.
A surprise here was, that single precision floats are not precise enough to do even these simplified simulations, which lead to various inconsistencies between the displayed path (which was simulated using fixed time steps) and the actual movement of the ship (which is simulated using Unity's Time.deltaTime) causing all sorts of problems. Trajectories that were predicated to fling-shot around a planet suddenly spiraled into the planet, orbits where unstable when they should be stable, stable ellipse trajectories around a planet converged to a circle and so on. In the end this took some gameplay adjustments ("it's not a bug, it's a feature") and some more math (kepler's equations) to get consistent results. The simulation and all the problems around it took one person easily over a day.
Learned Lesson
Develop your ideas further early on, invest some more time into researching solutions and possible complications around your key problems (here universe creation and simulation). Toying around and cycles through various, possibly vastly different, approaches during the jam, possibly needing massive refactorings will slow you down and will introduce lot's of subtle bugs.
Hey fellow gamedevs,
We are a team of four german students. We name ourselfs “Banana4Life” and have developed the game “Legendary Legionnaire Winter Massacre” for the third ludum dare we took part in. I (Jonas) made a quick LetsPlay of it here:
http://youtu.be/P8tznk-l52E
You can rate and play our game here: Legendary Legionnaire Winter Massacre
But now lets get to the post-mortem. Like last time we didn’t have huge problems and got even more stuff done than last time. But lets start with what went right.
What went right?
- The game was playable and apparently fun to play.
- We all met up at one place and were really productive.
- We developed a cool idea during the game. Things like unicorns and aliens were spontaneous ideas.
- The graphics were developed steadily parallel to the code and thus weren’t a product of the last minute.
- We implemented our core gameplay first and after that improved upon it.
- We partly had a lot of features that we wanted to implement, but cut the right features at the right time.
- We slept a reasonable amount of time (and weren’t completely destroyed after the weekend).
As you see the most important parts went right and I think we did a pretty good job developing the game this time. But we had some small problems anyway.
What went wrong?
- We didn’t have the final idea from the beginning on and had a hard time with the theme.
- There were a few graphical features I wanted to implement, like random props(grass, stones, …), that I did not have time for.
- Not all of us could work on the game for the whole third day, because they had to go to university.
- The rendering of the walls and floor tiles could have been solved better.
Most of the “What went wrong?” stuff could be solved with more time and maybe some more structured code on my side rendering the wall and floor tiles. (But it worked anyway)
What we want to do better?
- Think a bit more before writing code. (maybe, maybe not)
So I think we have an action plan for the next time.
- Try long enough to come up with a good idea.
- Make the game.
- Play more games.
- Enjoy the internet fame.
I hoped you liked our short writeup.
Greetings,
Team Banana4Life
P.S.: Play and rate our game please.
Hey guys,
5 hours left and I am streaming how I create the sounds for our game.
http://www.twitch.tv/bananafourlife
What sound does an unicorn make if it dies :/ :D Greetings!
Stream: http://www.twitch.tv/bananafourlife
Hey Guys,
I am really desperate. Could someone tell me why I have in one post a cool media inclusion and in the next it won’t work. That’s really really annoying. :(
This time it was a challenge for me to create music which fits in the theme. But finally I am finished!
https://soundcloud.com/rahtainka/legendary-legionnaire-winter
Now I will focusing on the sounds and maybe stream a little bit.
Our stream: http://www.twitch.tv/bananafourlife
Greetings!
Hey Guys,
here an update. Our game has an name: Legendary Legionnaire Winter Massacre
Story: “A legionnaire had build a snowman.
Suddenly aliens destroy it.
Take your revenge!”
You could hear the beta musicversion on our stream: http://www.twitch.tv/bananafourlife
Previous screenshots:
Greetings :)
Hey guys,
we are back and our stream is online: http://www.twitch.tv/bananafourlife !
Greetings form Germany,
Team Banana4life
https://soundcloud.com/rahtainka/ludum-dare-31-061214-2126
First snippet of music but i think i couldn’t use it… sadly :(
But it doesn’t fit to our theme. Next try…
Live Stream: http://www.twitch.tv/bananafourlife
Hey guys,
We are four students from Germany. It’s the third time we join the contest. Our last game at Ludum Dare 30 was Disconnect: http://ludumdare.com/compo/ludum-dare-30/?action=preview&uid=41477 . This time we will use following tools and technologies:
Programming Language / Engine: Java / libgdx
IDE: IntelliJ
Version Control / GUI: git / SmartGit
Graphics: GraphicsGale
Sound: Garageband
Streaming: OBS
Our stream will be in german language. You can find it at http://www.twitch.tv/bananafourlife . We have a shared twitter account https://twitter.com/bananafourlife where we will post when we will stream. Just follow us to see the hottest news about our streams.
Have a nice Ludum Dare 31,
Team Banana4Life
Hey fellow gamedevs,
We are a team of four german students. We name ourselfs “Banana4Life” and have developed the game “Disconnect” for the second ludum dare we took part in. I (Jonas) made a quick LetsPlay of it here:
https://www.youtube.com/watch?v=-To3KiIhNrA
You can rate and play our game here: Disconnect
But now lets get to the post-mortem. We didn’t have huge problems this time, after we spend half of the time developing a game that we threw away and started over last time. But lets start with what went right.
What went right?
- The game was playable and apparently fun to play.
- We had a cool idea from the start up and didn’t change it later on.
- The graphics and music / sounds were developed steadily parallel to the code and thus weren’t a product of the last minute.
- We implemented our core gameplay first and after that improved upon it.
- We partly had a lot of features that we wanted to implement, but we cut the right features.
- We slept a reasonable amount of time and weren’t completely destroyed after the weekend.
As you see the most important parts went right and I think we did a pretty good job developing the game this time. But we had some small problems anyway.
What went wrong?
- We spent a lot of time working on collision detecting fixing it over and over but it never really worked.
- At the end time ran out and the one level we had is pretty short.
- One of our developers worked remote and wasn’t in one room with the other people which made communication harder.
- Not all of us could work on the game on the third day, because they had to go to work.
- The rendering of the walls could have been solved better.
- Again the collisions were really annoying. Especially with syncing the player positions.
- We didn’t play enough games
Most of the “What went wrong?” stuff could be solved with more time and maybe some more structured code on my side rendering the walls. (But it worked anyway)
What we want to do better?
- Meet up all in one location
- Maybe implement a little framework for the collisions or use an existing framework, because that would be a huge timesaver.
- Take a day off the next day so everybody can work on the game the whole time.
- Think a bit more before writing code. (maybe, maybe not)
- Play more games
So I think we have an action plan for the next time.
- Prep a bit more by chosing a physics framework or something like this
- Try long enough to come up with a good idea. (Like we did this time)
- Make the game.
- Play more games.
- Enjoy the internet fame.
I hoped you liked our short writeup. Greetings,
Team Banana4Life
P.S.: Play and rate our game please.
Hey guys,
We are a german team consisting of 4 members. We just submitted our game “Disconnect”.
You play two players that are in two different worlds, but were connected by evil scientists. Now they can only move when the other person can move too. They only have a disconnector that allows them to wander around independently for a short time before the energy goes out. You need to find the endless powersource, developed in the same lab, to be able to disconnect and free the two forever. But be aware of the guards walking around.
I (Jonas) made a short made a playthrough of our game for you to watch:
https://www.youtube.com/watch?v=-To3KiIhNrA&feature=youtu.be
Have fun with our entry,
Team Banana4Life
Twitter: @bananafourlife
Hey folks,
We are streaming at jonasdann. At the moment its painting some graphics. Later down the line we will stream some dev.
Greetings,
Team Banana4Life
Hello Ludum Dare folks,
We are four students from Germany. After entering Ludum Dare 28 with a slightly other lineup, we are now back in the game. Last time we submitted #YOGO Platform (The theme was “You Only Got One”). This time we will use following tools and technologies:
Programming Language / Engine: Java / libgdx
IDE: IntelliJ
Version Controll / GUI: git / SmartGit
Graphics: Photoshop
Sound: Garageband
Streaming: OBS
Our streams will be in german language. You can find them at jonasdann and pschichtel. We have a shared twitter account where we will post when we will stream. Just follow us to see the hottest news about our streams.
Have a nice Ludum Dare 30,
Team Banana4Life
