From: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire) Newsgroups: comp.os.msdos.djgpp Subject: Re: Tile based games engine Date: 28 Jul 1997 06:49:44 GMT Organization: The National Capital FreeNet Lines: 216 Message-ID: <5rhfe8$qaj@freenet-news.carleton.ca> References: Reply-To: ao950 AT FreeNet DOT Carleton DOT CA (Paul Derbyshire) NNTP-Posting-Host: freenet6.carleton.ca To: djgpp AT delorie DOT com DJ-Gateway: from newsgroup comp.os.msdos.djgpp Precedence: bulk Write your own. I have written no fewer than three, all of which (eventually) worked perfectly. One was even a complicated Sonic Hedgehog type situation where tiles had properties such as surface normals. In a Zelda type tile, you want to create your own tile engine with two types of data file, or maybe three. Mine with Allegro have three. File #1: Tile File (properties). For each *species* of tile, one entry, which is something you could call struct tile. The file can have the simple binary structure: four bytes, long unsigned int, number of species; call this n, and then n of struct tile. Legend of Zelda III: A Link to the Past has numerous tile species I have identified. Some form groupins, i.e. four or nine part trees form the big trees depending on their offset relative to the tile center points. Forget that complex stuff for now. The underworld is generally simple. -Wall tiles: several wall tiles that look different and act the same: they cannot be penetrated by characters or objects like projectiles. Their different-looking species are combined to make a three-d look to the walls. The tile is still 2D! -Floor tiles: some are walkable. Some are not; like a tile containing a chest. There are several of them: a tile that blocks characters and passes projectiles with an open chest, generated at run time when a chest is opened, and many closed chest species, corresponding to different chest contents. Some species that block characters and pass projectiles are the ones with the little railing barriers. Other special floor tiles include the edge-of-pit tiles with the ragged edge look, which repel characters mildly toward the floor, so some effort is needed (momentum) to jump in, and ones without this border, as in the centers of pits and at some edges. These are further divided by if they take health and knock you to the last door, or drop you a level to somewhere useful. There were also tile groups for the jars, for teleports, for water, for those torch objects, and so forth. A simple tile struct might be: struct tilestr { bool characters_can_pass; bool projectiles_can_pass; int leftwall; // For tiles that block: furthest left point you can go in // the tile from the right. A complete wall has the // rightmost position, i.e. 31 in a 32x32 tile. A small // obstruction at the left of the tile has leftwall, say, 4, // and rightwall 0, so all of the tile is accessible but the // leftmost five columns of pixels. int rightwall, northwall, southwall; bool makes_cool_watery_sound_when_walked_on; bool is_hole; int hole_destination // A map index (see below) or -1 for a death/damage pit bool is_stairs; bool stairs_up; // false is down int stairs_x,stairs_y; // direction of stairs, north east south or west, // 0,1; 1,0; 0,-1; -1,0 int stairs_dest; // never -1!!! BITMAP *image[4] // Four pointers to animation phases that // alternate; all the same means no animation. }; The editor should have a new tile, edit tile, delete tile function group for working with tiles. The bitmaps might best be made with Paint Shop or something, the editor just asking for a filename of a .PCX or .BMP, which turns into the BITMAP pointed at. The file can be read with a single igetl and N fread (sizeof struct tile)s. Pack_fread can be used also, with Allegro packfiles. Writing it after editing is analogous. Then there is a Tile Bitmap File. A grabber file doesn't allow easy editing later. Better is a megabitmap: a bitmap very long, or very tall, a tile in one dimension and many in the other, holding the tile bitmaps. (A big pile of single bitmaps can be used too, but I discovered the hard way this makes for very slow loading of game and editor alike when there are numerous tiles.) These can be extracted using allegro blit() into individual bitmaps in the pointers. The editor can allocate a new bigger bitmap for writing the tiles, tigether with newly created tiles, back to disk. The editor and game can ditch the original megabitmap after separation is done. Another possibility is to omit the integer N from the tile file (making it a fixed length record file suitable for random access, although with modern computers, RAM, and DJGPP you would prefer to load the tile file into structs in RAM!) and obtain N instead by the w (or the h) member of the BITMAP you get from reading the tile bitmap file. Lastly, there are the MAP files. A MAP file consists of two 4-byte unsigned integers, the width and height in tiles (not pixels!). The rest is an MxN two-dimensional array of ints that are the indexes into the tile array of the tile in that position of the map. One map is distinguished as the start place of the player. The maps are interlinked by doors and stairs (and in a Zeldalike overworld, edges). Thus a map might have some other data following the array, such as the map reached if you walk off each edge, in a consistent order (NESW for example). Tiles like stairs and teleports can store a destination map number and an X and Y (in tiles) of the arrival point. Doors can be implemented as merely passable tiles at the borders of enclosed maps, so that the NESW edge method is used to determine destination. Note this makes some very odd, unrealistic but fascinating, playable, and possibly challenging kinds of topology for the game! A Moebius strip, weirdly connected forms, and even the Klein bottle can be made, along with the more mundate bounded planes, bounded rings, and toruses by choosing which maps act as neighbors at edges. Two stairs could even lead to two different maps from one map, in the same direction, as though it were a 4-D world with two up-down and two lateral dimensions! I have not tried any of these exotic topologies but I have observed them in some tile-based platform games, notably Faxanadu for the old (8-bit!) NES. To make a working game, of course, sprites are needed. Sprites can be in a characteristic file/bitmaps file binary also. Maps must have in their files, or in associated files, start points and maybe also generation points for sprites. A start point emits the sprite and becomes inert when the player scrolls it into view on a map. If the sprite is not killed and the player leaves, the start point becomes active again, meaning the enemy or object is still hanging around that area. (Or, it can wander out-of-sight for more elaborate games, utilizing more elaborate enemy and friend AI.) A killed sprite can leave the start point permanently inert. Alternatively, the sprite point can be reactivated after sufficient time or distance is achieved. (In the Zeldas, enemies in mazes come back in a room after about sixty seconds after death, or if you leave the dungeon and re-enter, and overworld ones regenerate as soon as you leave the map they are on, as an example. By contrast, in Mario IV, a vertical tile game, the enemies are permanently destroyed, with a few exceptions, but still come back if the entire level is replayed, or you die. Some games regenerate enemies after sufficient distance is achieved, such as more than ten maps away in the network of maps. As a computer scientist, I have constructed an order-n^2 algorithm for precomputing the minimum network distance between nodes in a network; iterate each node from a master list, and for each, recursively traverse the network, using an array for each node to hold results. Starting from node i, at depth d in recursion node j is reached; mark element j of i's array with value d. If j is reached again from i by another route, at a d2 => d, ignore j and proceed with other nodes. if d2 =d criterion leads to the algorithm backing itself into a corner, whereupon the next node after i is done.) Generation points can also be made. A generation point makes a species of sprite periodically on a timer, or at random intervals greater than a minimum interval. These might be an endless flood of enemies, or projectiles as in some kind of gun. Generation points can also be implemented not as points in a Map but as sprites. Then they may (or may not) move and may (or may not) be killable. (Note the lasers in Zelda III underworld! These move and don't die. Ones that move and die can be regarded as enemies with a projectile weapon.) Another possibility is a real-world-ish mechanism. Each map tracks the number of enemies on it and has a maximum and a list of species and relative abundances found in that part of the world. Initially, there are no enemies. At random but minimally-separated intervals, the computer picks a map, picks a species weighted by the abundances, and puts a new enemy of that point as a latent sprite at a random but unobstructed location on the map, failing to act if there is either no unobstructed point or a maximal number of enemies already present. This mimicks real-world behaviors, where in a typical ecosystem, predators die or are killed, and more are born, with an equilibrium population persisting typically. This also means the enemies are continually regenerated and there is no danger of the player ending up with a "dry game", with all enemies dead but puzzles unsolved in the area currently accessible to the player. This also allows interesting twists of fate and programming, i.e. making some maps in frequently traversed areas have primarily weak enemies, but a tiny abundance or likelihood of a bigger enemy, like a midboss, turning up unexpectedly. This could challenge the player and throws some interesting aspects of chance into a game. (This goes well with a save-game feature, especially with a large, complex, and long-duration game!) Obviously there should be a point the player must cross before a particular stronger type of enemy can pop up in such places. A midboss should not turn up until *the* midboss of that species has been defeated in its major lair, and that level or goal thus passed. Otherwise the plotline is screwed up by the player encountering a critter out of normal timing, the midboss encounter then seeming anticlimactic; and there is a risk of the player being caught well before the level sufficient to defeat the creature, in which case the guy will probably be mangled thoroughly and indisputably in a one-sided battle. Imagine playing Zelda III and encountering the rhinobeetle boss species of dungeon 4 before getting the hammer or bombs! Obviously also, a pivotal boss, including the end boss and perhaps other bosses with integral plot roles, enemies of a species characterised by only one instantiation, should never be made to pop up elsewhere. Zelda III would make no sense with the occasional extra Agahnim or Ganon. (An extra Ganon prior to the silver arrows would also be a particularly and spectacularly disastrous example of the aforementioned no-win scenario danger. And, of course, an end boss in the middle of the first level, with code to automatically end the game when it is dead, and defeatable with difficulty at that stage, could cause a truncated game, which is another seriously losing situation from the player's point of view. An unexpected and ridiculous win, like an unexpected and ridiculous loss, makes a player feel gypped, though perhaps to a lesser extent. A rather peculiar bug of this general type is observed in actuality in the 3D tile based game Rise of the Triad. There is a secret (hard-to-reach and un-needed for winning) level containing a copy of a later mission's end boss, which is not a random generation but oddly enough a deliberate inclusion by the map maker; killing it successfully (which involves a miracle) results in ROTT screaming and dying with a particularly obtuse error message: "Boss destroyed on illegal level." This is anticlimactic, and also a game show-stopper, and decidedly odd. My hypothesis is that this "bug" is a feature designed to trap players using codes, since that enemy is very hard to reach and almost unkillable without them! But I digress.) In any event, the basis for a simple tile based system with maps, tile properties, and tile bitmaps in separate files, has been described above, and it is not hard to implement. Info on the nature, usage, and representation in more files of sprites has been given and some other useful tidbits like the shortest-path algorithm for networks and details of some pitfalls of certain techniques if implemented suboptimally. -- .*. Where feelings are concerned, answers are rarely simple [GeneDeWeese] -() < When I go to the theater, I always go straight to the "bag and mix" `*' bulk candy section...because variety is the spice of life... [me] Paul Derbyshire ao950 AT freenet DOT carleton DOT ca, http://chat.carleton.ca/~pderbysh