I have a small pet project. One of the biggest challenges in it is to generate a random ships combination for the given game board. Turned out it isn't a trivial task and I have to apply dynamic programming in order to find the result. It takes decent amount of time especially when there isn't solution for the case.
static placeShips(col: number, row: number, placedShips: Ship[], shipsToPlace: ShipTypeAbstract[]): Ship[]|null {
Grid.iter++
if (shipsToPlace.length === 0) {
return placedShips
}
const grid = Grid.initGrid(col, row)
placedShips.forEach((ship: Ship) => {
grid.placeShipWithSurrounding(ship)
})
const types = [...shipsToPlace]
const shipType = types.pop()
const orientations = Math.random() > 0.5 ? [true, false] : [false, true]
for (const isHorizontal of orientations) {
const maxCol = isHorizontal ? grid.cols - shipType.getSize() : grid.cols
const maxRow = isHorizontal ? grid.rows : grid.rows - shipType.getSize()
const randomRowOffset = Math.floor(Math.random() * maxRow)
for (var r = 0; r < maxRow; r++) {
var rr = r + randomRowOffset
if (rr >= maxRow) {
rr -= maxRow
}
const randomColOffset = Math.floor(Math.random() * maxCol)
for (var c = 0; c < maxCol; c++) {
if (Grid.iter > row * col * 50) {
throw new Error(`In ${Grid.iter} iteration we weren't able to fit all ships`)
}
var cc = c + randomColOffset
if (cc >= maxCol) {
cc -= maxCol
}
const ship = new Ship(new Position(cc, rr), isHorizontal, shipType)
if (grid.canPlace(ship) === true) {
const pl = [...placedShips]
pl.push(ship)
const res = Grid.placeShips(col, row, pl, [...types])
if (res !== null) {
return res
}
}
}
}
}
return null
}
I will do my best optimizing this piece of code (will add memorization, presort input ships array, optimize loops, etc) but it will always be time consuming unless I find completely different approach.
I run performance test and got expected result:
$ wrk -t 10 -c50 -d10s --timeout 1m http://localhost:3000/shuffle/PdgFRR
Running 10s test @ http://localhost:3000/shuffle/PdgFRR
10 threads and 50 connections
Thread Stats Avg Stdev Max +/- Stdev
Latency 3.65s 1.54s 5.74s 70.41%
Req/Sec 2.06 2.18 10.00 92.63%
98 requests in 10.09s, 51.22KB read
Requests/sec: 9.71
Transfer/sec: 5.08KB
For more or less tricky ships combination it is able to handle only 10 requests per second. As far as I can understand (I am a PHP developer and the pet project aim is to get along with nodejs) the method blocks the main thread.
In order to solve this issue I would like to apply partitioning approach (pass small chunks of work to setTimeout or setImmediate functions) but the problem is that I have no idea how to split dynamic programming loop into chunks. Any clue how to achieve this goal?
P.S. I assume I am doing something wrong because such simple game requires so much computation. There are plenty much more fancy games which generate the whole game world on the fly. Chess for example, calculates thousands steps on each turn.
your solution is a recursive brute force one. It will be pretty slow in any language. Of cource it would be faster in case you don't allocate dynamic memory so often or if you rewrite it in fast language like c/c++/rust. There is a possibility to import and use native modules functionalities inside of nodejs.
Chunkifying the computation
if you wish to split single complex task into parts relatively easilly you can do something like this: replace all of your class methods to async for example static async placeShips(. in this case these functions returns will be wrapped in a Promise as now method internals could teoretically be asynchronious and non blocking the main thread. inside of async function it is possible to use await keyword to unwrap value from a Promise.
const res = await Grid.placeShips(col, row, pl, [...types]);
this way all the pieces of the implementation will be scheduled via promises and that means microtasks=tasks with larger priorities than macrotasks.
to insert some less prioritised scheduling mechanism we can use setTimeout and wrap it into the promise api to use it easily inside of async function
const waitNextEventLoopCycle = () => new Promise(resolve => setTimeout(resolve, 0));
// shorter but less explicit implementation
const waitLoop = () => new Promise(setTimeout);
and usage whenever you decie to make a small stop for current process (better not to make it too often, because every usage would slow down the execution of this job a bit)
await waitLoop()
this technique has a little usage in the real world, but if you can avoid it - you'd better avoid it. It is also not perfect in recursive solutions as it is hard to find points where you want to stop, without doing it too many times. If you had billions iterations loop for example, you could have stopped at lets say every 100 millions and it would be pretty obvious and effective.
Worth trying would be to allocate a separate thread or process to handle the task for the particular query. Modules node:worker_threads(threads), node:child_process or node:cluster(processes) can help here.
however in real world in majority of projects (in some cases because a lot of devs aren't familliar with js or nodejs platform) there spawned a bunch of simillar nodejs server processes and some other software piece is used to dispatch work for those processes.