Passed
Push — master ( 280472...400146 )
by Vincent
04:09
created

cellSightBlocking(int,int)   A

Complexity

Conditions 3

Size

Total Lines 10
Code Lines 5

Duplication

Lines 0
Ratio 0 %

Code Coverage

Tests 3
CRAP Score 3.1406

Importance

Changes 1
Bugs 0 Features 0
Metric Value
cc 3
eloc 5
c 1
b 0
f 0
dl 0
loc 10
ccs 3
cts 4
cp 0.75
crap 3.1406
rs 10
1
/*
2
 * This file is part of ArakneUtils.
3
 *
4
 * ArakneUtils is free software: you can redistribute it and/or modify
5
 * it under the terms of the GNU Lesser General Public License as published by
6
 * the Free Software Foundation, either version 3 of the License, or
7
 * (at your option) any later version.
8
 *
9
 * ArakneUtils is distributed in the hope that it will be useful,
10
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12
 * GNU Lesser General Public License for more details.
13
 *
14
 * You should have received a copy of the GNU Lesser General Public License
15
 * along with ArakneUtils.  If not, see <https://www.gnu.org/licenses/>.
16
 *
17
 * Copyright (c) 2017-2020 Vincent Quatrevieux
18
 */
19
20
package fr.arakne.utils.maps;
21
22
/**
23
 * Utility class for compute line of sights
24
 * Note: The used algorithm is not exactly same as the client's one, some differences can occurs
25
 *
26
 * Algorithm :
27
 * - Get coordinates of the two cells
28
 * - "draw" a line between the cells :
29
 * - Compute the vector between those cells
30
 * - Creates the function : Y = ySlope * X + yAtZero with
31
 * - For each X between the cells compute the related Y using the function
32
 * - Increments Y cell by cell to reach the computed Y
33
 * - Check the cell line of sight value
34
 * - If the sight is blocked, return false
35
 *
36
 * @param <C> The battlefield cell type
37
 */
38
final public class LineOfSight<C extends BattlefieldCell> {
39
    final private DofusMap<C> battlefield;
40
    final private int width; // store map width for optimisation
41
42 1
    public LineOfSight(DofusMap<C> battlefield) {
43 1
        this.battlefield = battlefield;
44 1
        this.width = battlefield.dimensions().width();
45 1
    }
46
47
    /**
48
     * Check the line of sight between those two cells
49
     *
50
     * @param source The source cell
51
     * @param target The target cell
52
     *
53
     * @return true if target is not blocked
54
     */
55
    public boolean between(C source, C target) {
56 1
        return between(new CoordinateCell<>(source), new CoordinateCell<>(target));
57
    }
58
59
    /**
60
     * Check the line of sight between those two cells
61
     *
62
     * @param source The source cell
63
     * @param target The target cell
64
     *
65
     * @return true if target is not blocked
66
     */
67
    public boolean between(CoordinateCell<C> source, CoordinateCell<C> target) {
68 1
        if (source.x() == target.x() && source.y() == target.y()) {
69 1
            return true;
70
        }
71
72 1
        if (source.x() == target.x()) {
73 1
            return checkWithSameX(source, target);
74
        }
75
76
        // Swap source and target to ensure that source.x < target.x
77 1
        if (source.x() > target.x()) {
78 1
            final CoordinateCell<C> tmp = source;
79
80 1
            source = target;
81 1
            target = tmp;
82
        }
83
84 1
        final int yDirection = source.y() > target.y() ? -1 : 1;
85 1
        final double ySlope = (double) (target.y() - source.y()) / (double) (target.x() - source.x());
86 1
        final double yAtZero = source.y() - ySlope * source.x();
87
88 1
        int currentY = source.y();
89
90
        // For every X between source and target
91 1
        for (int currentX = source.x(); currentX <= target.x(); ++currentX) {
92
            // yMax is the value of Y at the current X
93 1
            int yMax = (int) Math.round((currentX + 0.5) * ySlope + yAtZero);
94
95
            for (;;) {
96
                // target is reached : do not check it's LoS
97 1
                if (currentX == target.x() && currentY == target.y()) {
98 1
                    return true;
99
                }
100
101
                // Ignore the source LoS
102 1
                if (currentX != source.x() || currentY != source.y()) {
103 1
                    if (cellSightBlocking(currentX, currentY)) {
104 1
                        return false;
105
                    }
106
                }
107
108
                // Increment Y until yMax is reached
109 1
                if (currentY == yMax) {
110 1
                    break;
111
                }
112
113 1
                currentY += yDirection;
114
            }
115
        }
116
117
        // Increments Y until target is reached
118
        for (; yDirection > 0 ? currentY < target.y() : currentY > target.y(); currentY += yDirection) {
119
            if (cellSightBlocking(target.x(), currentY)) {
120
                return false;
121
            }
122
        }
123
124
        return true;
125
    }
126
127
    /**
128
     * Check the line of sight value for a single cell by its coordinates
129
     *
130
     * @return true if the cell block the line of sight
131
     */
132
    private boolean cellSightBlocking(int x, int y) {
133
        // https://github.com/Emudofus/Dofus/blob/1.29/ank/battlefield/utils/Pathfinding.as#L550
134 1
        final int cellId = x * width + y * (width - 1);
135
136
        // Cell outside the battlefield
137 1
        if (cellId >= battlefield.size() || cellId < 0) {
138
            return false;
139
        }
140
141 1
        return battlefield.get(cellId).sightBlocking();
142
    }
143
144
    /**
145
     * Check line of sight with aligned cells
146
     */
147
    private boolean checkWithSameX(CoordinateCell<C> source, CoordinateCell<C> target) {
148 1
        final int startY = Math.min(source.y(), target.y());
149 1
        final int endY = Math.max(source.y(), target.y());
150
151
        // Ignore the first and last cells
152 1
        for (int currentY = startY + 1; currentY < endY; ++currentY) {
153 1
            if (cellSightBlocking(target.x(), currentY)) {
154 1
                return false;
155
            }
156
        }
157
158 1
        return true;
159
    }
160
}
161