Return to Question

My goal is to reach 60 frames per second for a full HD grid with 8x8 (in pixel) tiles. Right now a full-screen grid composed of 16x16 tiles (1920x1080) renders with 60, but 8x8 tiles have abysmal speed.

I profiled my algorithm and fixed the bottlenecks but now I've reached the limits of Swing itself. This application works with layers composed of Tile objects (with a corresponding Position) so you can imagine a whole thing as a 3D map composed of Tiles with x, y and z coordinates.

My current algorithm works like this:

I fetch the Renderable objects. These are text gui components, layers, etc.
I render them onto a FastTileGraphics object (this uses arrays for speed).
I divide them into chunks according to the parallelism parameter to achieve parallel decomposition of work.
I group the Tiles into vertical vectors (I do this because I need to support transparency and tiles can be rendered on top of each other).
If an opaque tile is encountered I overwrite the list since in that case I only need to render a single Tile at that position.
I render the tiles onto BufferedImages in parallel.
Then I render these images onto the Canvas.

The implementation looks like this:

override fun render() {
 val now = SystemUtils.getCurrentTimeMs()
 val bs: BufferStrategy = canvas.bufferStrategy // this is a regular Swing Canvas object
 val parallelism = 4
 val interval = tileGrid.width / (parallelism - 1)
 val tilesToRender = mutableListOf<MutableMap<Position, MutableList<Pair<Tile, TilesetResource>>>>()
 0.until(parallelism).forEach { _ ->
 tilesToRender.add(mutableMapOf())
 }
 val renderables = tileGrid.renderables // TileGrid supplies the renderables that contain the tiles
 for (i in renderables.indices) {
 val renderable = renderables[i]
 if (!renderable.isHidden) {
 val graphics = FastTileGraphics(
 initialSize = renderable.size,
 initialTileset = renderable.tileset,
 initialTiles = emptyMap()
 )
 renderable.render(graphics)
 graphics.contents().forEach { (tilePos, tile) ->
 val finalPos = tilePos + renderable.position
 val idx = finalPos.x / interval
 tilesToRender[idx].getOrPut(finalPos) { mutableListOf() }
 if (tile.isOpaque) {
 tilesToRender[idx][finalPos] = mutableListOf(tile to renderable.tileset)
 } else {
 tilesToRender[idx][finalPos]?.add(tile to renderable.tileset)
 }
 }
 }
 }
 canvas.bufferStrategy.drawGraphics.configure().apply {
 color = Color.BLACK
 fillRect(0, 0, tileGrid.widthInPixels, tileGrid.heightInPixels)
 tilesToRender.map(::renderPart).map { it.join() }.forEach { img ->
 drawImage(img, 0, 0, null)
 }
 dispose()
 }
 bs.show()
 lastRender = now
}
private fun renderPart(
 tilesToRender: MutableMap<Position, MutableList<Pair<Tile, TilesetResource>>>
): CompletableFuture<BufferedImage> = CompletableFuture.supplyAsync {
 val img = BufferedImage(
 tileGrid.widthInPixels,
 tileGrid.heightInPixels,
 BufferedImage.TRANSLUCENT
 )
 val gc = img.graphics.configure()
 for ((pos, tiles) in tilesToRender) {
 for ((tile, tileset) in tiles) {
 renderTile(
 graphics = gc,
 position = pos,
 tile = tile,
 tileset = tilesetLoader.loadTilesetFrom(tileset)
 )
 }
 }
 img
}
private fun Graphics.configure(): Graphics2D {
 this.color = Color.BLACK
 val gc = this as Graphics2D
 gc.setRenderingHint(RenderingHints.KEY_ANTIALIASING, RenderingHints.VALUE_ANTIALIAS_OFF)
 gc.setRenderingHint(RenderingHints.KEY_RENDERING, RenderingHints.VALUE_RENDER_SPEED)
 gc.setRenderingHint(RenderingHints.KEY_DITHERING, RenderingHints.VALUE_DITHER_ENABLE)
 gc.setRenderingHint(RenderingHints.KEY_TEXT_ANTIALIASING, RenderingHints.VALUE_TEXT_ANTIALIAS_OFF)
 gc.setRenderingHint(RenderingHints.KEY_FRACTIONALMETRICS, RenderingHints.VALUE_FRACTIONALMETRICS_OFF)
 gc.setRenderingHint(RenderingHints.KEY_ALPHA_INTERPOLATION, RenderingHints.VALUE_ALPHA_INTERPOLATION_SPEED)
 gc.setRenderingHint(RenderingHints.KEY_COLOR_RENDERING, RenderingHints.VALUE_COLOR_RENDER_QUALITY)
 return gc
}
private fun renderTile(
 graphics: Graphics2D,
 position: Position,
 tile: Tile,
 tileset: Tileset<Graphics2D>
) {
 if (tile.isNotEmpty) {
 tileset.drawTile(tile, graphics, position)
 }
}

Renderable looks like this, it just accepts a TileGraphics for rendering:

interface Renderable : Boundable, Hideable, TilesetOverride {
 /**
 * Renders this [Renderable] onto the given [TileGraphics] object.
 */
 fun render(graphics: TileGraphics)
}

TileGraphics looks like this:

interface TileGraphics {
 val tiles: Map<Position, Tile>
 fun draw(
 tile: Tile,
 drawPosition: Position
 )
}

and Tileset is an object that loads the textures from the filesystem and draws individual tiles on a surface (Graphics2D in our case):

interface Tileset<T : Any> {
 fun drawTile(tile: Tile, surface: T, position: Position)
}

surface here represents the grapics object we use to draw. This is necessary because there is also a LibGDX renderer that works differently. There are also multiple kinds of Tilesets, this is how a regular monospace font is rendered:

override fun drawTile(tile: Tile, surface: Graphics2D, position: Position) {
 val s = tile.asCharacterTile().get().character.toString()
 val fm = surface.getFontMetrics(font)
 val x = position.x * width
 val y = position.y * height
 surface.font = font
 surface.color = tile.backgroundColor.toAWTColor()
 surface.fillRect(x, y, resource.width, resource.height)
 surface.color = tile.foregroundColor.toAWTColor()
 surface.drawString(s, x, y + fm.ascent)
}

This algorithm runs for ~22ms.

I've profiled the whole thing and a major bottleneck is the drawing part:

tilesToRender.map(::renderPart).map { it.join() }.forEach { img ->
 drawImage(img, 0, 0, null)
}

If I remove those 3 lines I get ~5ms runtime (so drawing takes ~17ms).

I also noticed that parallel decomposition doesn't help at all. If I remove all parallelism I get similar results. Increasing parallelism results in an FPS drop.

The second biggest bottleneck is the grouping code (the graphics.contents().forEach { (tilePos, tile) -> part), it takes around ~4.5ms.

The numbers in total:

21.696576799999985 <-- all
5.328403500000007 <-- without drawing
4.575503500000005 <-- without any java 2d graphics operations
0.08593370000000009 <-- without grouping

How can I optimize this algorithm? The only part that's mandatory is rendering the renderables: renderable.render(graphics) but I already optimized it and it only takes ~0.8ms, so that's negligible.

java swing kotlin canvas

lang-java