1 /* Copyright (C) 2013-2014 Michal Brzozowski (rusolis@poczta.fm)
2
3 This file is part of KeeperRL.
4
5 KeeperRL is free software; you can redistribute it and/or modify it under the terms of the
6 GNU General Public License as published by the Free Software Foundation; either version 2
7 of the License, or (at your option) any later version.
8
9 KeeperRL is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
10 even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License along with this program.
14 If not, see http://www.gnu.org/licenses/ . */
15
16 #include "stdafx.h"
17
18 #include "field_of_view.h"
19 #include "square.h"
20 #include "square_array.h"
21 #include "level.h"
22 #include "position.h"
23
24 template <class Archive>
serialize(Archive & ar,const unsigned int)25 void FieldOfView::serialize(Archive& ar, const unsigned int) {
26 if (Archive::is_saving::value) // don't save the visibility values, as they can be easily recomputed
27 visibility = Table<unique_ptr<Visibility>>(visibility.getBounds());
28 ar(level, visibility, vision);
29 }
30
SERIALIZABLE(FieldOfView)31 SERIALIZABLE(FieldOfView)
32
33 template <class Archive>
34 void FieldOfView::Visibility::serialize(Archive& ar, const unsigned int) {
35 ar(visible, visibleTiles, px, py);
36 }
37
38 SERIALIZABLE(FieldOfView::Visibility)
SERIALIZATION_CONSTRUCTOR_IMPL(FieldOfView)39 SERIALIZATION_CONSTRUCTOR_IMPL(FieldOfView)
40 SERIALIZATION_CONSTRUCTOR_IMPL2(FieldOfView::Visibility, Visibility)
41
42 FieldOfView::FieldOfView(WLevel l, VisionId v)
43 : level(l), visibility(l->getBounds()), vision(v) {
44 }
45
canSee(Vec2 from,Vec2 to)46 bool FieldOfView::canSee(Vec2 from, Vec2 to) {
47 if ((from - to).lengthD() > sightRange)
48 return false;
49 if (!visibility[from])
50 visibility[from].reset(new Visibility(level, vision, from.x, from.y));
51 return visibility[from]->checkVisible(to.x - from.x, to.y - from.y);
52 }
53
squareChanged(Vec2 pos)54 void FieldOfView::squareChanged(Vec2 pos) {
55 vector<Vec2> updateList;
56 if (!visibility[pos])
57 visibility[pos].reset(new Visibility(level, vision, pos.x, pos.y));
58 vector<Vec2> visible = visibility[pos]->getVisibleTiles();
59 for (Vec2 v : visible)
60 if (visibility[v] && visibility[v]->checkVisible(pos.x - v.x, pos.y - v.y)) {
61 visibility[v].reset();
62 }
63 }
64
setVisible(WConstLevel level,int x,int y)65 void FieldOfView::Visibility::setVisible(WConstLevel level, int x, int y) {
66 if (level->inBounds(Vec2(px + x, py + y)) &&
67 !visible[x + sightRange][y + sightRange] && x * x + y * y <= sightRange * sightRange) {
68 visible[x + sightRange][y + sightRange] = 1;
69 visibleTiles.push_back(Vec2(px + x, py + y));
70 }
71 }
72
73 static int totalIter = 0;
74 static int numSamples = 0;
75
Visibility(WLevel level,VisionId vision,int x,int y)76 FieldOfView::Visibility::Visibility(WLevel level, VisionId vision, int x, int y) : px(x), py(y) {
77 memset(visible, 0, (2 * sightRange + 1) * (2 * sightRange + 1));
78 calculate(2 * sightRange, 2 * sightRange,2 * sightRange, 2,-1,1,1,1,
79 [&](int px, int py) { return !Position(Vec2(x + px, y + py), level).canSeeThru(vision); },
80 [&](int px, int py) { setVisible(level, px, py); });
81 calculate(2 * sightRange, 2 * sightRange,2 * sightRange, 2,-1,1,1,1,
82 [&](int px, int py) { return !Position(Vec2(x + py, y - px), level).canSeeThru(vision); },
83 [&](int px, int py) { setVisible(level, py, -px); });
84 calculate(2 * sightRange, 2 * sightRange,2 * sightRange,2,-1,1,1,1,
85 [&](int px, int py) { return !Position(Vec2(x - px, y - py), level).canSeeThru(vision); },
86 [&](int px, int py) { setVisible(level, -px, -py); });
87 calculate(2 * sightRange, 2 * sightRange,2 * sightRange,2,-1,1,1,1,
88 [&](int px, int py) { return !Position(Vec2(x - py, y + px), level).canSeeThru(vision); },
89 [&](int px, int py) { setVisible(level, -py, px); });
90 setVisible(level, 0, 0);
91 /* ++numSamples;
92 totalIter += visibleTiles.size();
93 if (numSamples%100 == 0)
94 INFO << numSamples << " iterations " << totalIter / numSamples << " avg";*/
95 }
96
getVisibleTiles() const97 const vector<Vec2>& FieldOfView::Visibility::getVisibleTiles() const {
98 return visibleTiles;
99 }
100
getVisibleTiles(Vec2 from)101 const vector<Vec2>& FieldOfView::getVisibleTiles(Vec2 from) {
102 if (!visibility[from]) {
103 visibility[from].reset(new Visibility(level, vision, from.x, from.y));
104 }
105 return visibility[from]->getVisibleTiles();
106 }
107
108
calculate(int left,int right,int up,int h,int x1,int y1,int x2,int y2,function<bool (int,int)> isBlocking,function<void (int,int)> setVisible)109 void FieldOfView::Visibility::calculate(int left, int right, int up, int h, int x1, int y1, int x2, int y2,
110 function<bool (int, int)> isBlocking, function<void (int, int)> setVisible){
111 if (y2*x1>=y1*x2) return;
112 if (h>up) return;
113 int leftx=x1, lefty=y1, rightx=x2, righty=y2;
114 int left_v=(int)floor((double)x1/y1*(h)),
115 right_v=(int)ceil((double)x2/y2*(h)),
116 left_b=(int)floor((double)x1/y1*(h-1)),
117 right_b=(int)ceil((double)x2/y2*(h+1));
118 if (left_v % 2)
119 ++left_v;
120 if (right_v % 2)
121 --right_v;
122 if(left_b % 2)
123 ++left_b;
124 if(right_b % 2)
125 --right_b;
126
127 if(left_b>=-left && left_b<=right && isBlocking(left_b/2,h/2)){
128 leftx=left_b+1;
129 lefty=h+(left_b>=0?-1:1);
130 }
131 if(left_v<-left) left_v=-left;
132 if(right_v>right) right_v=right;
133 bool prevBlocking = false;
134 for (int i=left_v/2;i<=right_v/2;++i){
135 setVisible(i, h / 2);
136 bool blocking = isBlocking(i, h / 2);
137 if(i > left_v / 2 && blocking && !prevBlocking)
138 calculate(left, right, up, h + 2, leftx, lefty, i * 2 - 1, h + (i<=0 ? -1:1), isBlocking, setVisible);
139 if(blocking){
140 leftx=i*2+1;
141 lefty=h+(i>=0?-1:1);
142 }
143 prevBlocking = blocking;
144 }
145 calculate(left, right, up, h + 2, leftx, lefty, rightx, righty, isBlocking, setVisible);
146 }
147
checkVisible(int x,int y) const148 bool FieldOfView::Visibility::checkVisible(int x, int y) const {
149 return x >= -sightRange && y >= -sightRange && x <= sightRange && y <= sightRange &&
150 visible[sightRange + x][sightRange + y] == 1;
151 }
152
153
154