Skip to content

Commit

Permalink
Fix, improve and optimize map saving logic
Browse files Browse the repository at this point in the history
  • Loading branch information
@SpaiR
SpaiR committed Jul 26, 2019
1 parent afc030e commit 272ddbc
Show file tree
Hide file tree
Showing 3 changed files with 115 additions and 59 deletions.
11 changes: 6 additions & 5 deletions .editorconfig
View file
Original file line number Diff line number Diff line change
@@ -1,8 1,9 @@
[*]
end_of_line=lf
indent_style=space
insert_final_newline=true
end_of_line = lf
indent_style = space
insert_final_newline = true

[*.{kt,kts}]
indent_size=4
max_line_length=140
indent_size = 4
max_line_length = 140
trim_trailing_whitespace = true
135 changes: 89 additions & 46 deletions src/main/kotlin/io/github/spair/strongdmm/logic/map/save/KeyGenerator.kt
View file
Original file line number Diff line number Diff line change
Expand Up @@ -5,77 5,120 @@ import kotlin.math.floor

class KeyGenerator(private val dmmData: DmmData) {

private val builder = StringBuilder()

companion object {
private const val BASE: Double = 52.0

// We can have only three tiers of keys, more here: https://secure.byond.com/forum/?post=2340796#comment23770802
private const val TIER_1_LIMIT: Int = 51 // a-Z
private const val TIER_2_LIMIT: Int = 2703 // aa-ZZ
private const val TIER_3_LIMIT: Int = 65535 // aaa-ymp
}
private const val TIER_3_LIMIT: Int = 65528 // aaa-ymi

// Calculated tiers with regard to 'a~' and 'a~~' keys
private const val REAL_TIER_1_LIMIT: Int = TIER_1_LIMIT
private const val REAL_TIER_2_LIMIT: Int = TIER_1_LIMIT TIER_2_LIMIT 1
private const val REAL_TIER_3_LIMIT: Int = REAL_TIER_2_LIMIT TIER_3_LIMIT 1

private val KEYS: Array<String> = Array(REAL_TIER_3_LIMIT 1) { "" }

init {
val builder = StringBuilder()
val base52keys = charArrayOf(
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
)

fun numToKey(num: Int, keyLength: Int): String {
var currentNum = num

do {
builder.insert(0, base52keys[currentNum % BASE.toInt()])
currentNum = floor(currentNum / BASE).toInt()
} while (currentNum > 0)

val lengthDiff = keyLength - builder.length

if (lengthDiff != 0) {
for (i in 0 until lengthDiff) {
builder.insert(0, 'a')
}
}

val result = builder.toString()
builder.clear()
return result
}

private val base52keys: CharArray = charArrayOf(
'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'
)
var index = 0

private val calculatedKeys: Array<String> = Array(TIER_3_LIMIT 1) { "" }
// a-Z
(0..TIER_1_LIMIT).forEach {
KEYS[index ] = numToKey(it, 1)
}

init {
(0..TIER_3_LIMIT).forEach { calculatedKeys[it] = numToKey(it) }
// aa-aZ
(0..TIER_1_LIMIT).forEach {
KEYS[index ] = numToKey(it, 2)
}

// ba-ZZ
((TIER_1_LIMIT 1)..TIER_2_LIMIT).forEach {
KEYS[index ] = numToKey(it, 2)
}

// aaa-aZZ
(0..TIER_2_LIMIT).forEach {
KEYS[index ] = numToKey(it, 3)
}

// baa-ymi
((TIER_2_LIMIT 1)..TIER_3_LIMIT).forEach {
KEYS[index ] = numToKey(it, 3)
}
}
}

fun createKey(): String {
val freeKeys = when {
dmmData.keyLength == 1 -> TIER_1_LIMIT
dmmData.keyLength == 2 -> TIER_2_LIMIT
else -> TIER_3_LIMIT
private lateinit var keysPool: MutableList<Int>
private var freeKeys: Int = 0

fun initKeysPool() {
keysPool = mutableListOf()

freeKeys = when {
dmmData.keyLength == 1 -> REAL_TIER_1_LIMIT
dmmData.keyLength == 2 -> REAL_TIER_2_LIMIT
else -> REAL_TIER_3_LIMIT
}

val keysPool = mutableListOf<String>()
val border = when (freeKeys) {
REAL_TIER_2_LIMIT -> REAL_TIER_1_LIMIT 1
REAL_TIER_3_LIMIT -> REAL_TIER_2_LIMIT 1
else -> 0
}

// Put all possible keys into the pool ...
for (num in 0..freeKeys) {
val key = calculatedKeys[num]
for (num in border..freeKeys) {
val key = KEYS[num]
if (!dmmData.hasTileContentByKey(key)) {
keysPool.add(key)
keysPool.add(num)
}
}
}

fun createKey(): String {
if (keysPool.isEmpty()) {
when (freeKeys) {
TIER_1_LIMIT -> throw RecreateKeysException(2)
TIER_2_LIMIT -> throw RecreateKeysException(3)
REAL_TIER_1_LIMIT -> throw RecreateKeysException(2)
REAL_TIER_2_LIMIT -> throw RecreateKeysException(3)
else -> throw IllegalStateException("Unable to create a new key. Limit of keys is exceeded.")
}
}

// ... and pick randomly from it
return keysPool[(0 until keysPool.size).random()]
}

private fun numToKey(num: Int): String {
var currentNum = num

do {
builder.insert(0, base52keys[currentNum % BASE.toInt()])
currentNum = floor(currentNum / BASE).toInt()
} while (currentNum > 0)

val lengthDiff = dmmData.keyLength - builder.length

if (lengthDiff != 0) {
for (i in 0 until lengthDiff) {
builder.insert(0, base52keys[0])
}
}

val result = builder.toString()
builder.clear()
return result
val index = (0 until keysPool.size).random()
val key = keysPool[index]
keysPool.removeAt(index)
return KEYS[key]
}
}
28 changes: 20 additions & 8 deletions src/main/kotlin/io/github/spair/strongdmm/logic/map/save/SaveMap.kt
View file
Original file line number Diff line number Diff line change
Expand Up @@ -2,7 2,6 @@ package io.github.spair.strongdmm.logic.map.save

import io.github.spair.dmm.io.DmmData
import io.github.spair.strongdmm.logic.Workspace
import io.github.spair.strongdmm.logic.map.CoordPoint
import io.github.spair.strongdmm.logic.map.Dmm
import java.io.File

Expand Down Expand Up @@ -102,34 101,47 @@ class SaveMap(private val dmm: Dmm) {
return // All locations have its own key
}

val locsWithoutKey = mutableListOf<CoordPoint>()
val locsWithoutKey = mutableListOf<Long>()

// Store two ints in one long. Yes, it matters. Yes, for performance reasons. No, don't repeat that at home.
fun setValue(x: Int, y: Int): Long = (x.toLong() shl 32) or (y.toLong() and 0xffffffffL)
fun getX(value: Long): Int = (value shr 32).toInt()
fun getY(value: Long): Int = value.toInt()

// Collect all locs without keys
for (y in outputDmmData.maxY downTo 1) {
for (x in 1..outputDmmData.maxX) {
val tileContent = dmm.getTileContentByLocation(x, y)

if (!outputDmmData.hasKeyByTileContent(tileContent)) {
locsWithoutKey.add(CoordPoint(x, y))
locsWithoutKey.add(setValue(x, y))
}
}
}

// Try to find the most appropriate key to the location
// Try to find the most appropriate key for location
for (unusedKey in unusedKeys.toSet()) {
for (loc in locsWithoutKey) {
if (dmm.initialDmmData.getKeyByLocation(loc.x, loc.y) == unusedKey) {
val x = getX(loc)
val y = getY(loc)
if (dmm.initialDmmData.getKeyByLocation(x, y) == unusedKey) {
unusedKeys.remove(unusedKey)
outputDmmData.addKeyAndTileContent(unusedKey, dmm.getTileContentByLocation(loc.x, loc.y))
outputDmmData.addKeyAndTileContent(unusedKey, dmm.getTileContentByLocation(x, y))
locsWithoutKey.remove(loc)
break
}
}
}

if (locsWithoutKey.isNotEmpty()) {
keyGenerator.initKeysPool()
}

// Handle remaining locations
for (loc in locsWithoutKey) {
val tileContent = dmm.getTileContentByLocation(loc.x, loc.y)
val x = getX(loc)
val y = getY(loc)
val tileContent = dmm.getTileContentByLocation(x, y)

if (outputDmmData.hasKeyByTileContent(tileContent)) {
continue
Expand All @@ -156,7 168,7 @@ class SaveMap(private val dmm: Dmm) {
// It's okay to recreate all keys from scratch when we overflow our limit.
// But when our limit was increased we can easily use it to represent the map even if it has two unique keys.
// At the same time, key length reduction will result in an abnormal map diff, which may result in a lot of conflicts.
// Thus the only case when Editor will reduce key length is when we have only one key on the map. Just because I can.
// Thus the only case when the Editor will reduce key length is when we have only one key on the map. Just because I can.
private fun trimSizeIfNeeded() {
if (outputDmmData.keys.size == 1) {
clearKeyAndTileContent()
Expand Down

0 comments on commit 272ddbc

Please sign in to comment.