2D sandbox adventure RPG with destructible and generated world.
This is open-source project - you can download latest version here - Github.com
- Destructible world - almost any piece of world can be destroyed.
- Generated world - there is no pre-built levels in the game - everything is generated (including quests, NPC's and etc).
- Advanced pixel-perfect physics + water physics
- 14 unique weapons - starting from pickaxe and ending by rocket launcher and plasma drill.
- Role-playing elements - your character have stats. You can invest points into stats thus making your character stronger, smarter, etc.
- Crafting - you can create items using blueprints on the workbench. Any item can be disassembled, modified, repaired.
- Social elements - you can talk and barter with NPC's. Your character have reputation, if you will be killing other dwarves you will get penalties on reputation and cannot trade with dwarves and enter into their houses.
- Bosses - on each location you can find a boss
You are a dwarf and you live in a deserted kingdom. For a long time your people lived in wealth and prosperity, but on some day a huge chunk of mysterious energetic crystals was found. These crystal were called Arkalith, they were used to create amazing machines and powerful weapons that allowed the kingdom to seize neighboring kingdoms. Your kingdom fell into decay after the discovery of the mysterious Black creature deep underground in the thick of the arkalith. The ancient creature immediately incinerated the dwarves who were mining this sinister mineral. After a while the kingdom was filled with deadly creatures from other worlds. Royal forces were not prepared for this strike - dwarves dying everyday since then, not so many of them can survive. Discovery of Arkalith also affected ordinary creatures - bees, frogs, bats - even ordinary bee became huge and dangerous. Swords and axes became useless, creatures from other worlds could be destroyed only by the energy of the arkalith. You is the only hope for your kingdom!
The main difference between my game and others: the game has fluid physics and requires very fast collision detection&response algorithm to grind up thousands of physical particles and calculate collision detection between those particles and millions of pixels.
In The Dwarf Adventure terrain represented as a rectangular image where each pixel contains color (R, G, B, 3 bytes) and some additional info – set of flags packed in 16-bit integer (2 bytes), so each pixel takes 5 bytes of memory.
The flags should be described more carefully. Each bit of a flag was used to give a pixel some property, for example:
As you can see it is very compact approach of storing properties of a pixel, especially when you have 100kk pixels – in this case the whole terrain will take only 476 Mb of memory, which is very low amount for modern hardware (just look at the memory amount consumed by your browser when you reading this article).
Circle was chosen as a shape of physical body – it is the simpliest shape, which allows checking collisions very fast. Circle shape allows doing a fluid simulation, which is another very interesting part of the game. More complex shapes, like polygons require more complex collision detection algorithms (like SAT and so on).
My very first algorithm was pretty straight-forward: iterate over every pixel in the terrain and check intersection between every physical body to find a push vector which will allow me to push body outside of “solid” parts of a terrain. As was expected, straight-forward approach was very slow and the game was totally unplayable: I was able to play with decent FPS only on small maps (1500x700px) with very little amount of physical bodies (less than 20-30) on quite powerful processor – 8 cores with 3.8 GHz, of course now I’m using only single core, but be patient – I’ll talk about multithreaded simulation quite soon. The main disadvantage of this approach is very obvious – we doing a lot of unnecessary operations: checking collisions with pixels that are too far away from physical bodies. So it the time to do optimizations!
Firstly, we should uniformly divide our terrain into a set of square cells of same size – I choose 256x256 pixels cell. Each cell will contain its portion of pixels of the terrain. And now we can modify our algorithm: instead of checking every pixel of the terrain, let’s firstly check intersection of a physical body with a terrain cell and if they are not intersecting we can discard a huge amount of pixels! With this very simple optimization, I increased performance up to 50 times!
But we can go further – modern processors have at least 2 cores nowadays and more commonly 4 cores. We can use this to check collisions in parallel. To do so, we can uniformly split a set of physical bodies into more small sets and do collision checks in different threads – each thread will use its own set of bodies. Such easy approach can speed up physics up to N times, where N – cores count of your processor. But I should mention that in real world you can speed up physics in (0.85N) times.
The game also have more specific optimizations: we can go further and divide terrain cell into set of smaller cells and each sub-cell will have pixels that are stored linearly in memory – this sort of optimization aimed to make calculations more cache-friendly.
That’s all for now, I would like to know if you interested in such kind of articles with technical details.
Thanks for reading!
No articles were found matching the criteria specified. We suggest you try the article list with no filter applied, to browse all available. Post article and help us achieve our mission of showcasing the best content from all developers. Join now to share your own content, we welcome creators and consumers alike and look forward to your comments.