Skip to content

Instantly share code, notes, and snippets.

@BradB132

BradB132/Cavegen_comparison.txt

Last active March 30, 2023 21:00
Show Gist options
  • Save BradB132/d23f11087eeb24a95b322b60de3dbe55 to your computer and use it in GitHub Desktop.
Save BradB132/d23f11087eeb24a95b322b60de3dbe55 to your computer and use it in GitHub Desktop.
Download ZIP
CaveGen performance comparison (Godot)
Raw
Cavegen_comparison.txt
// BEGIN GDSCRIPT - Takes >9000ms.
extends TextureRect
const map_dimension: int = 1024
enum MapType { AIR = 0, ROCK = 1 }
var map_array: PackedInt32Array
var temp_array: PackedInt32Array
func _ready():
map_array = PackedInt32Array()
map_array.resize(map_dimension * map_dimension)
temp_array = PackedInt32Array()
temp_array.resize(map_array.size())
_randomize(0.5)
for i in 5:
_smooth5x5()
for i in 3:
_smooth3x3()
# This logic is for visualization only, not included in timing.
if OS.is_debug_build():
var float_array = PackedFloat32Array()
float_array.resize(map_array.size())
for i in map_array.size():
float_array[i] = float(map_array[i])
var image = Image.create_from_data(map_dimension, map_dimension, false, Image.FORMAT_RF, float_array.to_byte_array())
texture = ImageTexture.create_from_image(image)
func _randomize(randomThreshold:float):
for x in map_dimension:
for y in map_dimension:
var type: MapType
if randf() > randomThreshold:
type = MapType.ROCK
else:
type = MapType.AIR
map_array[x+y*map_dimension] = type
func _smooth3x3():
temp_array.clear()
temp_array.append_array(map_array)
var max_index = map_dimension-2
var wallType = MapType.ROCK
for x in range(2,max_index):
for y in range(2,max_index):
var currentIndex = x+y*map_dimension
var wallCount:int = 0
var rowIndex1 = (currentIndex-map_dimension)-1
if temp_array[rowIndex1] & wallType:
wallCount += 1
if temp_array[rowIndex1+1] & wallType:
wallCount += 1
if temp_array[rowIndex1+2] & wallType:
wallCount += 1
if temp_array[currentIndex-1] & wallType:
wallCount += 1
if temp_array[currentIndex+1] & wallType:
wallCount += 1
var rowIndex5 = (currentIndex+map_dimension)-1
if temp_array[rowIndex5] & wallType:
wallCount += 1
if temp_array[rowIndex5+1] & wallType:
wallCount += 1
if temp_array[rowIndex5+2] & wallType:
wallCount += 1
if wallCount > 4:
map_array[currentIndex] = MapType.ROCK
elif wallCount < 4:
map_array[currentIndex] = MapType.AIR
func _smooth5x5():
temp_array.clear()
temp_array.append_array(map_array)
var max_index = map_dimension-2
var wallType = MapType.ROCK
for x in range(2,max_index):
for y in range(2,max_index):
var currentIndex = x+y*map_dimension
var wallCount:int = 0
var rowIndex1 = (currentIndex-2*map_dimension)-2
if temp_array[rowIndex1] & wallType:
wallCount += 1
if temp_array[rowIndex1+1] & wallType:
wallCount += 1
if temp_array[rowIndex1+2] & wallType:
wallCount += 1
if temp_array[rowIndex1+3] & wallType:
wallCount += 1
if temp_array[rowIndex1+4] & wallType:
wallCount += 1
var rowIndex2 = (currentIndex-map_dimension)-2
if temp_array[rowIndex2] & wallType:
wallCount += 1
if temp_array[rowIndex2+1] & wallType:
wallCount += 1
if temp_array[rowIndex2+2] & wallType:
wallCount += 1
if temp_array[rowIndex2+3] & wallType:
wallCount += 1
if temp_array[rowIndex2+4] & wallType:
wallCount += 1
if temp_array[currentIndex-2] & wallType:
wallCount += 1
if temp_array[currentIndex-1] & wallType:
wallCount += 1
if temp_array[currentIndex+1] & wallType:
wallCount += 1
if temp_array[currentIndex+2] & wallType:
wallCount += 1
var rowIndex4 = (currentIndex+map_dimension)-2
if temp_array[rowIndex4] & wallType:
wallCount += 1
if temp_array[rowIndex4+1] & wallType:
wallCount += 1
if temp_array[rowIndex4+2] & wallType:
wallCount += 1
if temp_array[rowIndex4+3] & wallType:
wallCount += 1
if temp_array[rowIndex4+4] & wallType:
wallCount += 1
var rowIndex5 = (currentIndex+2*map_dimension)-2
if temp_array[rowIndex5] & wallType:
wallCount += 1
if temp_array[rowIndex5+1] & wallType:
wallCount += 1
if temp_array[rowIndex5+2] & wallType:
wallCount += 1
if temp_array[rowIndex5+3] & wallType:
wallCount += 1
if temp_array[rowIndex5+4] & wallType:
wallCount += 1
if wallCount > 15:
map_array[currentIndex] = MapType.ROCK
elif wallCount < 10:
map_array[currentIndex] = MapType.AIR
// END GDSCRIPT
// NAIVE C++ START - Takes ~470ms
// begin .hpp
#ifndef WAVE_MAP_H
#define WAVE_MAP_H
#include <godot_cpp/classes/canvas_layer.hpp>
enum TileType : uint8_t {
TileType_AIR = 0,
TileType_ROCK = 1,
};
namespace godot {
class WaveMap : public CanvasLayer {
GDCLASS(WaveMap, CanvasLayer);
public:
void _ready() override;
protected:
static void _bind_methods() {}
private:
static const int32_t mapDimension = 1024;
uint8_t _mapArray[mapDimension*mapDimension];
uint8_t _tempArray[mapDimension*mapDimension];
void smooth3x3();
void smooth5x5();
};
}
#endif // WAVE_MAP_H
// Begin .cpp
#include "WaveMap.hpp"
#include <godot_cpp/variant/utility_functions.hpp>
static const double randomThreshold = 0.5;
void godot::WaveMap::_ready() {
// Randomize the map.
for (size_t i = 0; i < mapDimension*mapDimension; i++) {
_mapArray[i] = UtilityFunctions::randf() > randomThreshold ? TileType_ROCK : TileType_AIR;
}
// Smooth.
for (size_t i = 0; i < 5; i++) {
smooth5x5();
}
for (size_t i = 0; i < 3; i++) {
smooth3x3();
}
}
void godot::WaveMap::smooth3x3() {
memcpy(_tempArray, _mapArray, sizeof(uint8_t)*mapDimension*mapDimension);
size_t maxIndex = mapDimension-2;
uint8_t wallMask = TileType_ROCK;
for (size_t x = 2; x < maxIndex; x++) {
for (size_t y = 2; y < maxIndex; y++) {
size_t currentIndex = x+y*mapDimension;
size_t row1Index = (currentIndex-mapDimension)-1;
size_t row3Index = (currentIndex+mapDimension)-1;
uint32_t wallCount = 0;
if (_tempArray[row1Index] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+2] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex-1] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex+1] & wallMask) {
wallCount++;
}
if (_tempArray[row3Index] & wallMask) {
wallCount++;
}
if (_tempArray[row3Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row3Index+2] & wallMask) {
wallCount++;
}
if (wallCount > 4) {
_mapArray[currentIndex] = TileType_ROCK;
} else if (wallCount < 4) {
_mapArray[currentIndex] = TileType_AIR;
}
}
}
}
void godot::WaveMap::smooth5x5() {
memcpy(_tempArray, _mapArray, sizeof(uint8_t)*mapDimension*mapDimension);
size_t maxIndex = mapDimension-2;
uint8_t wallMask = TileType_ROCK;
for (size_t x = 2; x < maxIndex; x++) {
for (size_t y = 2; y < maxIndex; y++) {
size_t currentIndex = x+y*mapDimension;
size_t row1Index = (currentIndex-2*mapDimension)-2;
size_t row2Index = (currentIndex-mapDimension)-2;
size_t row4Index = (currentIndex+mapDimension)-2;
size_t row5Index = (currentIndex+2*mapDimension)-2;
uint32_t wallCount = 0;
if (_tempArray[row1Index] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+2] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+3] & wallMask) {
wallCount++;
}
if (_tempArray[row1Index+4] & wallMask) {
wallCount++;
}
if (_tempArray[row2Index] & wallMask) {
wallCount++;
}
if (_tempArray[row2Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row2Index+2] & wallMask) {
wallCount++;
}
if (_tempArray[row2Index+3] & wallMask) {
wallCount++;
}
if (_tempArray[row2Index+4] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex-2] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex-1] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex+1] & wallMask) {
wallCount++;
}
if (_tempArray[currentIndex+2] & wallMask) {
wallCount++;
}
if (_tempArray[row4Index] & wallMask) {
wallCount++;
}
if (_tempArray[row4Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row4Index+2] & wallMask) {
wallCount++;
}
if (_tempArray[row4Index+3] & wallMask) {
wallCount++;
}
if (_tempArray[row4Index+4] & wallMask) {
wallCount++;
}
if (_tempArray[row5Index] & wallMask) {
wallCount++;
}
if (_tempArray[row5Index+1] & wallMask) {
wallCount++;
}
if (_tempArray[row5Index+2] & wallMask) {
wallCount++;
}
if (_tempArray[row5Index+3] & wallMask) {
wallCount++;
}
if (_tempArray[row5Index+4] & wallMask) {
wallCount++;
}
if (wallCount > 15) {
_mapArray[currentIndex] = TileType_ROCK;
} else if (wallCount < 10) {
_mapArray[currentIndex] = TileType_AIR;
}
}
}
}
// END NAIVE C++
// BRANCHLESS C++ START - Takes ~230ms
// begin .hpp
#ifndef WAVE_MAP_H
#define WAVE_MAP_H
#include <godot_cpp/classes/canvas_layer.hpp>
enum TileType : uint8_t {
TileType_AIR = 0,
TileType_ROCK = 1,
};
namespace godot {
class WaveMap : public CanvasLayer {
GDCLASS(WaveMap, CanvasLayer);
public:
void _ready() override;
protected:
static void _bind_methods() {}
private:
static const int32_t mapDimension = 1024;
uint8_t _mapArray[mapDimension*mapDimension];
uint8_t _tempArray[mapDimension*mapDimension];
void smooth3x3();
void smooth5x5();
};
}
#endif // WAVE_MAP_H
// Begin .cpp
#include "WaveMap.hpp"
#include <godot_cpp/variant/utility_functions.hpp>
static const double randomThreshold = 0.5;
void godot::WaveMap::_ready() {
// Randomize the map.
for (size_t i = 0; i < mapDimension*mapDimension; i++) {
_mapArray[i] = UtilityFunctions::randf() > randomThreshold ? TileType_ROCK : TileType_AIR;
}
// Smooth.
for (size_t i = 0; i < 5; i++) {
smooth5x5();
}
for (size_t i = 0; i < 3; i++) {
smooth3x3();
}
}
void godot::WaveMap::smooth3x3() {
memcpy(_tempArray, _mapArray, sizeof(uint8_t)*mapDimension*mapDimension);
size_t maxIndex = mapDimension-2;
uint8_t wallMask = TileType_ROCK;
for (size_t x = 2; x < maxIndex; x++) {
for (size_t y = 2; y < maxIndex; y++) {
size_t currentIndex = x+y*mapDimension;
size_t row1Index = (currentIndex-mapDimension)-1;
size_t row3Index = (currentIndex+mapDimension)-1;
// Calculate using branchless predication.
uint32_t wallCount =
(uint32_t)((_tempArray[row1Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+2] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex-1] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row3Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row3Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row3Index+2] & wallMask) != 0);
_mapArray[currentIndex] =
(wallCount > 4) * TileType_ROCK +
(wallCount < 4) * TileType_AIR +
(wallCount == 4) * _mapArray[currentIndex];
}
}
}
void godot::WaveMap::smooth5x5() {
memcpy(_tempArray, _mapArray, sizeof(uint8_t)*mapDimension*mapDimension);
size_t maxIndex = mapDimension-2;
uint8_t wallMask = TileType_ROCK;
for (size_t x = 2; x < maxIndex; x++) {
for (size_t y = 2; y < maxIndex; y++) {
size_t currentIndex = x+y*mapDimension;
size_t row1Index = (currentIndex-2*mapDimension)-2;
size_t row2Index = (currentIndex-mapDimension)-2;
size_t row4Index = (currentIndex+mapDimension)-2;
size_t row5Index = (currentIndex+2*mapDimension)-2;
// Calculate using branchless predication.
uint32_t wallCount =
(uint32_t)((_tempArray[row1Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+2] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+3] & wallMask) != 0) +
(uint32_t)((_tempArray[row1Index+4] & wallMask) != 0) +
(uint32_t)((_tempArray[row2Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row2Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row2Index+2] & wallMask) != 0) +
(uint32_t)((_tempArray[row2Index+3] & wallMask) != 0) +
(uint32_t)((_tempArray[row2Index+4] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex-2] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex-1] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex+1] & wallMask) != 0) +
(uint32_t)((_tempArray[currentIndex+2] & wallMask) != 0) +
(uint32_t)((_tempArray[row4Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row4Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row4Index+2] & wallMask) != 0) +
(uint32_t)((_tempArray[row4Index+3] & wallMask) != 0) +
(uint32_t)((_tempArray[row4Index+4] & wallMask) != 0) +
(uint32_t)((_tempArray[row5Index] & wallMask) != 0) +
(uint32_t)((_tempArray[row5Index+1] & wallMask) != 0) +
(uint32_t)((_tempArray[row5Index+2] & wallMask) != 0) +
(uint32_t)((_tempArray[row5Index+3] & wallMask) != 0) +
(uint32_t)((_tempArray[row5Index+4] & wallMask) != 0);
_mapArray[currentIndex] =
(wallCount > 15) * TileType_ROCK +
(wallCount < 10) * TileType_AIR +
(wallCount <= 15 && wallCount >= 10) * _mapArray[currentIndex];
}
}
}
// END BRANCHLESS C++
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment