Help with algorithm to dynamically update text display.

Question

First, some backstory:

I'm making what may amount to be a "roguelike" game so i can exersize some interesting ideas i've got floating around in my head. The gameplay isn't going to be a dungeon crawl, but in any case, the display is going to be done in a similar fasion, with simple ascii characters.

Being that this is a self exercise, I endeavor to code most of it myself.

Eventually I'd like to have the game runnable on arbitrarily large game worlds. (to the point where i envision havening the game networked and span over many monitors in a computer lab).

Right now, I've got some code that can read and write to arbitrary sections of a text console, and a simple partitioning system set up so that i can path-find efficiently.

---

And now the question:

I've ran some benchmarks, and the biggest bottleneck is the re-drawing of text consoles.

Having a game world that large will require an intelligent update of the display. I don't want to have to re-push my entire game buffer every frame... I need some pointers on how to set it up so that it only draws sections of the game have have been updated. (and not just individual characters as I've got now)

I've been manipulating the windows console via windows.h, but I would also be interested in getting it to run on linux machines over a puTTY client connected to the server.

I've tried adapting some video-processing routines, as there is nearly a 1:1 ratio between pixel and character, but I had no luck.

Really I want a simple explanation of some of the principles behind it. But some example (psudo)code would be nice too.

Answer 1

I am not going to claim to understand this, but I believe this is close to the issue behind James Gosling's legendary Gosling Emacs redrawing code. See his paper, titled appropriately, "A Redisplay Algorithm", and also the general string-to-string correction problem.

Answer 2

Use Curses, or if you need to be doing it yourself, read about the VTnnn control codes. Both of these should work on windows and on *nix terms and consoles (and Windows). You can also consult the nethack source code for hints. This will let you change characters on the screen wherever changes have happened.

Answer 3

Having a game world that large will require an intelligent update of the display. I don't want to have to re-push my entire game buffer every frame... I need some pointers on how to set it up so that it only draws sections of the game have have been updated. (and not just individual characters as I've got now)

The size of the game world isn't really relevant, as all you need to do is work out the visible area for each client and send that data. If you have a typical 80x25 console display then you're going to be sending just 2 or 3 kilobytes of data each time, even if you add in colour codes and the like. This is typical of most online games of this nature: update what the person can see, not everything in the world.

If you want to experiment with trying to find a way to cut down what you send, then feel free to do that for learning purposes, but we're about 10 years past the point where it is inefficient to update a console display in something approaching real time and it would be a shame to waste time fixing a problem that doesn't need fixing. Note that the PDF linked above gives an O(ND) solution whereas simply sending the entire console is half of O(N), where N is defined as the sum of the lengths of A and B and D.