From 56708986473f869b158469ce9ef16754d245d89f Mon Sep 17 00:00:00 2001 From: Elronnd Date: Tue, 2 Jan 2018 01:03:01 -0800 Subject: [PATCH] Add code for 'my algorithm' (not actually written by me but by adam milazzo). Crashes right now --- src/constants.d | 2 + src/game.d | 38 ++++-- src/glyph.d | 4 + src/graphix0.d | 7 +- src/item.d | 14 ++- src/myfov.d | 354 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 398 insertions(+), 21 deletions(-) create mode 100644 src/myfov.d diff --git a/src/constants.d b/src/constants.d index 9af61c7..b0aa649 100644 --- a/src/constants.d +++ b/src/constants.d @@ -9,5 +9,7 @@ enum Action { MoveNorth, MoveSouth, MoveLeft, MoveRight, MoveNorthLeft, MoveNorthRight, MoveSouthLeft, MoveSouthRight, Wait, Printloc, + Pickup, + Showinv, Quit } diff --git a/src/game.d b/src/game.d index 1e97b30..c8c64b7 100644 --- a/src/game.d +++ b/src/game.d @@ -4,10 +4,11 @@ import BearLibTerminal; import colour; import constants; -import fov; +import myfov; import glyph; import graphix; import graphix0; +import item; import logging; import mapgen; import map; @@ -24,6 +25,7 @@ abstract class Being { Vector2n loc; RGBColour fgcolour, bgcolour; Glyph glyph; + Item[] inventory; private struct _attr { bool reverse, italic, bold, underline; } _attr attrs; @@ -71,14 +73,7 @@ class You: Being { this.glyph = Glyph.at; } override Action getaction() { - - // TODO gdc doesn't like RedBlackTrees. But someday it will - version (GNU) { - //static immutable bool[int] vikeys = ['h': 1, 'j': 1, 'k': 1, 'l': 1, 'y': 1, 'u': 1, 'b': 1, 'n': 1, 'q': 1, '.', 'w': 1]; - bool[dchar] vikeys = ['h': 1, 'j': 1, 'k': 1, 'l': 1, 'y': 1, 'u': 1, 'b': 1, 'n': 1, 'q': 1, '.': 1, 'w': 1]; - } else { - static immutable auto vikeys = set!dchar('h', 'j', 'k', 'l', 'y', 'u', 'b', 'n', 'q', '.', 'w'); - } + static immutable auto vikeys = set!dchar('h', 'j', 'k', 'l', 'y', 'u', 'b', 'n', 'q', '.', 'w'); Action tmp; dchar c; @@ -119,6 +114,12 @@ class You: Being { case 'w': // (w)here am I? tmp = Action.Printloc; break; + case ',': + tmp = Action.Pickup; + break; + case 'i': + tmp = Action.Showinv; + break; default: assert(0); } return tmp; @@ -133,16 +134,17 @@ class You: Being { class Game { Being u; Being[] mons; + Item[] items; Graphics1 graphics; Map map; this(string[] args) { - graphics = new Default_chargfx!SDL0(this); + graphics = new Default_chargfx!BLT0(this); this.map = genmap(MapType.caves); mons = [u = new You(graphics)]; - foreach (_; 1..10) { + foreach (_; 1 .. 100) { mons ~= new Mon(); } @@ -159,6 +161,18 @@ class Game { } while ((!map[m.loc].walkable) || !mon_at(m.loc)); } + + foreach (_; 1 .. 100) { + import std.random: choice; + items ~= choice(all_items); + } + foreach (ref i; items) { + do { + i.loc.x = rn1(map_x+1); + i.loc.y = rn1(map_y+1); + } while (!map[i.loc].walkable); + } + u.glyph = Glyph.at; } @@ -331,7 +345,7 @@ class Game { deltay = deltax = 0; } refresh(); - do_fov(map, u.loc.x, u.loc.y, 100, true); + do_fov(map, u.loc.x, u.loc.y, 100/*, true*/); } graphics.close(); } diff --git a/src/glyph.d b/src/glyph.d index 6fbb4f0..020fbb5 100644 --- a/src/glyph.d +++ b/src/glyph.d @@ -4,6 +4,10 @@ enum Glyph: dchar { hash = '#', middot = '·', at = '@', + paren_left = '(', paren_right = ')', + brace_left = '{', brace_right = '}', + bracket_left = '[', bracket_right = ']', + light_square = '░', /* they have gradients of how bright they are, but that's * handled elsewhere */ medium_square = '▒', diff --git a/src/graphix0.d b/src/graphix0.d index 7ffebbf..36affd4 100644 --- a/src/graphix0.d +++ b/src/graphix0.d @@ -53,7 +53,6 @@ class SDL0: CharGfx0 { return false; } - TTF_SetFontHinting(font, TTF_HINTING_NONE); TTF_SetFontKerning(font, 0); ushort[2] text; @@ -109,11 +108,11 @@ class SDL0: CharGfx0 { */ - //SDL_SetHint(SDL_HINT_RENDER_SCALE_QUALITY, "0"); + SDL_SetHint(SDL_HINT_RENDER_SCALE_QUALITY, "1"); // Title, bunch of stuff, resolution, borderless fullscreen // SDL_WINDOW_FULLSCREEN actually changes the video mode - sdl_window = SDL_CreateWindow(null, SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 0, 0, SDL_WINDOW_BORDERLESS | SDL_WINDOW_FULLSCREEN_DESKTOP); + sdl_window = SDL_CreateWindow(null, SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 0, 0, SDL_WINDOW_FULLSCREEN_DESKTOP); if (!sdl_window) { sdlerror(); } // sdl_window = SDL_CreateWindow("", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, 0, 0, SDL_WINDOW_FULLSCREEN | SDL_WINDOW_FULLSCREEN_DESKTOP); renderer = SDL_CreateRenderer(sdl_window, -1, SDL_RENDERER_ACCELERATED | SDL_RENDERER_PRESENTVSYNC); @@ -321,7 +320,7 @@ class BLT0: CharGfx0 { uint maxy() { return terminal.state(terminal.keycode.height); } void settitle(string title) { - terminal.setf("window.title=%s", title); + //terminal.setf("window.title=%s", title); } void mvaddch(dchar ch, uint y, uint x, RGBColour fg, RGBColour bg, bool bold, bool italic, bool underline, bool reverse) { diff --git a/src/item.d b/src/item.d index a5043a3..ca4b7b3 100644 --- a/src/item.d +++ b/src/item.d @@ -1,7 +1,8 @@ -import glyph; import colour; -import util; +import glyph; import graphix; +import map; +import util; enum Item_type { Weapon, @@ -15,19 +16,22 @@ enum Item_type { struct Item { Item_type type; string name; + Glyph glyph; void delegate(ref Item self, Graphics1 graphics) _on_pick_up; void delegate(ref Item self, Graphics1 grahpics) _on_use; mixin funcwrapper!_on_pick_up; mixin funcwrapper!_on_use; + + Vector2n loc; } -Item[] items; +Item[] all_items; shared static this() { - items = [ - Item(Item_type.Weapon, "long sword", (ref Item self, Graphics1 graphics) { graphics.pline("Hmmm. On the one hand I think you picked up a%d " ~ self.name ~ ". On the other hand I think you're a bloody idiot.", 7); }), + all_items = [ + Item(Item_type.Weapon, "long sword", Glyph.paren_right, (ref Item self, Graphics1 graphics) { graphics.pline("Hmmm. On the one hand I think you picked up a%d " ~ self.name ~ ". On the other hand I think you're a bloody idiot.", 7); }), ]; } diff --git a/src/myfov.d b/src/myfov.d new file mode 100644 index 0000000..6fda29d --- /dev/null +++ b/src/myfov.d @@ -0,0 +1,354 @@ +import map; + +// Adam Milazzo's "my algorithm" for FOV. Adapted from the c# code at http://www.adammil.net/blog/v125_Roguelike_Vision_Algorithms.html + +void do_fov(ref Map map, uint x, uint y, int rangeLimit) { + map.for_all((ref Tile x) => x.visible = false); + + map[y, x].visible = true; + foreach (octant; 0 .. 8) { + compute(map, octant, Point(x, y), rangeLimit, 1, Slope(1, 1), Slope(0, 1)); + } +} + +// represents the slope Y/X as a rational number +private struct Slope { + int x, y; + + bool greater(int y, int x) { return this.y*x > this.x*y; } // this > y/x + bool greater_or_equal(int y, int x) { return this.y*x >= this.x*y; } // this >= y/x + bool less(int y, int x) { return this.y*x < this.x*y; } // this < y/x + bool less_or_equal(int y, int x) { return this.y*x <= this.x*y; } // this <= y/x +} + +private struct Point { + int x, y; +} + + +private void compute(ref Map map, int octant, Point origin, int rangeLimit, int x, Slope top, Slope bottom) { + // NOTE: the code duplication between blocks_light and set_visible is for performance. don't refactor the octant + // translation out unless you don't mind an 18% drop in speed + bool blocks_light(int x, int y, int octant, Point origin) { + int nx = origin.x, ny = origin.y; + switch(octant) { + case 0: nx += x; ny -= y; break; + case 1: nx += y; ny -= x; break; + case 2: nx -= y; ny -= x; break; + case 3: nx -= x; ny -= y; break; + case 4: nx -= x; ny += y; break; + case 5: nx -= y; ny += x; break; + case 6: nx += y; ny += x; break; + case 7: nx += x; ny += y; break; + default: break; + } + return map[ny, nx].blocks_light; + } + + void set_visible(int x, int y, int octant, Point origin) { + int nx = origin.x, ny = origin.y; + switch(octant) { + case 0: nx += x; ny -= y; break; + case 1: nx += y; ny -= x; break; + case 2: nx -= y; ny -= x; break; + case 3: nx -= x; ny -= y; break; + case 4: nx -= x; ny += y; break; + case 5: nx -= y; ny += x; break; + case 6: nx += y; ny += x; break; + case 7: nx += x; ny += y; break; + default: break; + } + map[ny, nx].visible = true; + } + + + + + + /* + * throughout this function there are references to various parts of tiles. a tile's coordinates refer to its + * center, and the following diagram shows the parts of the tile and the vectors from the origin that pass through + * those parts. given a part of a tile with vector u, a vector v passes above it if v > u and below it if v < u + * g center: y / x + * a------b a top left: (y*2+1) / (x*2-1) i inner top left: (y*4+1) / (x*4-1) + * | /\ | b top right: (y*2+1) / (x*2+1) j inner top right: (y*4+1) / (x*4+1) + * |i/__\j| c bottom left: (y*2-1) / (x*2-1) k inner bottom left: (y*4-1) / (x*4-1) + *e|/| |\|f d bottom right: (y*2-1) / (x*2+1) m inner bottom right: (y*4-1) / (x*4+1) + * |\|__|/| e middle left: (y*2) / (x*2-1) + * |k\ /m| f middle right: (y*2) / (x*2+1) a-d are the corners of the tile + * | \/ | g top center: (y*2+1) / (x*2) e-h are the corners of the inner (wall) diamond + * c------d h bottom center: (y*2-1) / (x*2) i-m are the corners of the inner square (1/2 tile width) + * h + */ + for(; x <= rangeLimit; x++) /* (x <= rangeLimit) == (rangeLimit < 0 || x <= rangeLimit) */ { + // compute the Y coordinates of the top and bottom of the sector. we maintain that top > bottom + int topY; + + // if top == ?/1 then it must be 1/1 because 0/1 < top <= 1/1. this is special-cased because top + // starts at 1/1 and remains 1/1 as long as it doesn't hit anything, so it's a common case + if(top.x == 1) { + topY = x; + // top < 1 + } else { + /* + * get the tile that the top vector enters from the left. since our coordinates refer to the center of the + * tile, this is (x-0.5)*top+0.5, which can be computed as (x-0.5)*top+0.5 = (2(x+0.5)*top+1)/2 = + * ((2x+1)*top+1)/2. since top == a/b, this is ((2x+1)*a+b)/2b. if it enters a tile at one of the left + * corners, it will round up, so it'll enter from the bottom-left and never the top-left + */ + // the Y coordinate of the tile entered from the left + topY = ((x*2-1) * top.y + top.x) / (top.x*2); + /* now it's possible that the vector passes from the left side of the tile up into the tile above before + * exiting from the right side of this column. so we may need to increment topY + */ + + // if the tile blocks light (i.e. is a wall)... + if (blocks_light(x, topY, octant, origin)) { + /* if the tile entered from the left blocks light, whether it + * passes into the tile above depends on the shape of the wall tile + * as well as the angle of the vector. if the tile has does not + * have a beveled top-left corner, then it is blocked. the corner is + * beveled if the tiles above and to the left are not walls. we can + * ignore the tile to the left because if it was a wall tile, the + * top vector must have entered this tile from the bottom-left + * corner, in which case it can't possibly enter the tile above. + * + * otherwise, with a beveled top-left corner, the slope of the + * vector must be greater than or equal to the slope of the vector + * to the top center of the tile (x*2, topY*2+1) in order for it to + * miss the wall and pass into the tile above + */ + if (top.greater_or_equal(topY*2+1, x*2) && !blocks_light(x, topY+1, octant, origin)) { + topY++; + } + } + // the tile doesn't block light + else { + /* since this tile doesn't block light, there's nothing to stop it + * from passing into the tile above, and it does so if the vector is greater than the + * vector for the bottom-right corner of the tile above. however, + * there is one additional consideration. later code in this method + * assumes that if a tile blocks light then it must be visible, so + * if the tile above blocks light we have to make sure the light + * actually impacts the wall shape. now there are three cases: + * + * 1) the tile above is clear, in which case the vector must be + * above the bottom-right corner of the tile above, + * + * 2) the tile above blocks light and does not have a beveled + * bottom-right corner, in which case the vector must be above + * the bottom-right corner, and + * + * 3) the tile above blocks light and does have a beveled bottom- + * right corner, in which case the vector must be above the bottom + * center of the tile above (i.e. the corner of the beveled edge). + * + * + * now it's possible to merge 1 and 2 into a single check, and we + * get the following: if the tile above and to the right is a wall, + * then the vector must be above the bottom-right corner. otherwise, + * the vector must be above the bottom center. this works because if + * the tile above and to the right is a wall, then there are two + * cases: + * + * 1) the tile above is also a wall, in which case we must check + * against the bottom-right corner, or + * + * 2) the tile above is not a wall, in which case the vector passes + * into it if it's above the bottom-right corner. + * + * + * so either way we use the bottom-right corner in that case. now, + * if the tile above and to the right is not a wall, then we again + * have two cases: + * + * 1) the tile above is a wall with a beveled edge, in which case we + * must check against the bottom center, or + * + * 2) the tile above is not a wall, in which case it will only be + * visible if light passes through the inner square, and the + * inner square is guaranteed to be no larger than a wall + * diamond, so if it wouldn't pass through a wall diamond then it + * can't be visible, so there's no point in incrementing topY + * even if light passes through the corner of the tile above. so + * we might as well use the bottom center for both cases. + */ + int ax = x*2; // center + + // use bottom-right if the tile above and right is a wall + if (blocks_light(x+1, topY+1, octant, origin)) { + ax++; + } + + if (top.greater(topY*2+1, ax)) { + topY++; + } + } + } + + int bottomY; + // if bottom == 0/?, then it's hitting the tile at Y=0 dead center. this is special-cased because + // bottom.y starts at zero and remains zero as long as it doesn't hit anything, so it's common + if(bottom.y == 0) { + bottomY = 0; + } + // bottom > 0 + else { + // the tile that the bottom vector enters from the left + bottomY = ((x*2-1) * bottom.y + bottom.x) / (bottom.x*2); + + /* + * code below assumes that if a tile is a wall then it's visible, so if the tile contains a wall we have to + * ensure that the bottom vector actually hits the wall shape. it misses the wall shape if the top-left corner + * is beveled and bottom >= (bottomY*2+1)/(x*2). finally, the top-left corner is beveled if the tiles to the + * left and above are clear. we can assume the tile to the left is clear because otherwise the bottom vector + * would be greater, so we only have to check above + */ + if (bottom.greater_or_equal(bottomY*2+1, + x*2) && + blocks_light(x, bottomY, octant, origin) && + !blocks_light(x, bottomY+1, octant, origin)) { + bottomY++; + } + } + + // go through the tiles in the column now that we know which ones could possibly be visible + int wasOpaque = -1; // 0:false, 1:true, -1:not applicable + + // use a signed comparison because y can wrap around when decremented + for (int y = topY; y >= bottomY; y--) { + // skip the tile if it's out of visual range + if (rangeLimit < 0 || get_distance(x, y) <= rangeLimit) { + bool isOpaque = blocks_light(x, y, octant, origin); + /* + * every tile where topY > y > bottomY is guaranteed to be visible. + * also, the code that initializes topY and bottomY guarantees that + * if the tile is opaque then it's visible. so we only have to do + * extra work for the case where the tile is clear and y == topY or + * y == bottomY. if y == topY then we have to make sure that the top + * vector is above the bottom-right corner of the inner square. + * if y == bottomY then we have to make sure that the bottom vector + * is below the top-left corner of the inner square + */ + bool isVisible = isOpaque || ((y != topY || top.greater(y*4-1, x*4+1)) && (y != bottomY || bottom.less(y*4+1, x*4-1))); + /* + * NOTE: if you want the algorithm to be either fully or mostly + * symmetrical, replace the line above with the following line (and + * uncomment the Slope.less_or_equal method). the line ensures that a + * clear tile is visible only if there's an unobstructed line to its + * center. if you want it to be fully symmetrical, also remove the + * "isOpaque ||" part and see NOTE comments further down + * + * bool isVisible = isOpaque || ((y != topY || top.greaterOrEqual(y, x)) && (y != bottomY || bottom.less_or_equal(y, x))); + */ + if (isVisible) { + set_visible(x, y, octant, origin); + } + + // if we found a transition from clear to opaque or vice versa, adjust the top and bottom vectors + // but don't bother adjusting them if this is the last column anyway + if (x != rangeLimit) { + if (isOpaque) { + // if we found a transition from clear to opaque, this sector is done in this column, + // so adjust the bottom vector upward and continue processing it in the next column + if (wasOpaque == 0) { + /* + * if the opaque tile has a beveled top-left + * corner, move the bottom vector up to the + * top center. otherwise, move it up to the + * top left. the corner is beveled if the + * tiles above and to the left are clear. we + * can assume the tile to the left is clear + * because otherwise the vector would be + * higher, so we only have to check the tile + * above + */ + int nx = x*2, ny = y*2+1; // top center by default + // NOTE: if you're using full symmetry and + // want more expansive walls (recommended), + // comment out the next line + + // top left if the corner is not beveled + if (blocks_light(x, y+1, octant, origin)) + nx--; + + // we have to maintain the invariant that top > bottom, so the new sector + // created by adjusting the bottom is only valid if that's the case + if (top.greater(ny, nx)) { + // if we're at the bottom of the column, + // then just adjust the current sector rather than recursing + // since there's no chance that this sector + // can be split in two by a later transition back to clear + if(y == bottomY) { + bottom = Slope(ny, nx); break; + } + // don't recurse unless necessary + else { + compute(map, octant, origin, rangeLimit, x+1, top, Slope(ny, nx)); + } + } + // the new bottom is greater than or equal + // to the top, so the new sector is empty + // and we'll ignore it. if we're at the + // bottom of the column, we'd normally + // adjust the current sector rather than + else { + // recursing, so that invalidates the current sector and we're done + if (y == bottomY) + return; + } + } + wasOpaque = 1; + } else { + // if we found a transition from opaque to clear, adjust the top vector downwards + if (wasOpaque > 0) { + // if the opaque tile has a beveled bottom- + // right corner, move the top vector down to + // the bottom center. otherwise, move it + // down to the bottom right. the corner is + // beveled if the tiles below and to the + // right are clear. we know the tile below + // is clear because that's the current tile, + // so just check to the right + + // the bottom of the opaque tile (oy*2-1) equals the top of this tile (y*2+1) + int nx = x*2, ny = y*2+1; + + // NOTE: if you're using full symmetry and + // want more expansive walls (recommended), + // comment out the next line + + // check the right of the opaque tile (y+1), not this one + if (blocks_light(x+1, y+1, octant, origin)) { + nx++; + } + + // we have to maintain the invariant that + // top > bottom. if not, the sector is empty + // and we're done + if (bottom.greater_or_equal(ny, nx)) { + return; + } + + top = Slope(ny, nx); + } + wasOpaque = 0; + } + } + } + } + + // if the column didn't end in a clear tile, then there's no reason to continue processing the current sector + // because that means either 1) wasOpaque == -1, implying that the sector is empty or at its range limit, or 2) + // wasOpaque == 1, implying that we found a transition from clear to opaque and we recursed and we never found + // a transition back to clear, so there's nothing else for us to do that the recursive method hasn't already. (if + // we didn't recurse (because y == bottomY), it would have executed a break, leaving wasOpaque equal to 0.) + if(wasOpaque != 0) { + break; + } + } +} + +private int get_distance(int x, int y) { + return x * x + y * y; +} -- 2.11.4.GIT