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.path; |
21
|
|
|
|
22
|
|
|
|
23
|
|
|
import fr.arakne.utils.encoding.Base64; |
24
|
|
|
import fr.arakne.utils.maps.DofusMap; |
25
|
|
|
import fr.arakne.utils.maps.MapCell; |
26
|
|
|
import fr.arakne.utils.maps.constant.Direction; |
27
|
|
|
|
28
|
|
|
import java.util.Optional; |
29
|
|
|
|
30
|
|
|
/** |
31
|
|
|
* Decode map data like paths or directions |
32
|
|
|
*/ |
33
|
|
|
final public class Decoder<C extends MapCell> { |
34
|
|
|
final private DofusMap<C> map; |
35
|
|
|
|
36
|
|
|
/** |
37
|
|
|
* @param map The map to handle |
38
|
|
|
*/ |
39
|
1 |
|
public Decoder(DofusMap<C> map) { |
40
|
1 |
|
this.map = map; |
41
|
1 |
|
} |
42
|
|
|
|
43
|
|
|
/** |
44
|
|
|
* Get the immediately next cell if we move by the given direction |
45
|
|
|
* If the next cell is out of the map, an empty optional is returned |
46
|
|
|
* |
47
|
|
|
* @param start The start cell |
48
|
|
|
* @param direction The direction to follow |
49
|
|
|
* |
50
|
|
|
* @return The next cell, wrapped into an optional. If the next cell is outside map, return an empty optional |
51
|
|
|
*/ |
52
|
|
|
public Optional<C> nextCellByDirection(C start, Direction direction) { |
53
|
1 |
|
int nextId = start.id() + direction.nextCellIncrement(map.dimensions().width()); |
54
|
|
|
|
55
|
1 |
|
if (nextId >= map.size() || nextId < 0) { |
56
|
1 |
|
return Optional.empty(); |
57
|
|
|
} |
58
|
|
|
|
59
|
1 |
|
return Optional.of(map.get(nextId)); |
60
|
|
|
} |
61
|
|
|
|
62
|
|
|
/** |
63
|
|
|
* Decode compressed path |
64
|
|
|
* |
65
|
|
|
* @param encoded The encoded path |
66
|
|
|
* @param start The start cell. Can be null. |
67
|
|
|
* Set a value is the encoded path do not contains the start cell (ex: use {@link Decoder#encode(Path, boolean)} with includeStartCell) |
68
|
|
|
* |
69
|
|
|
* @return The path, with list of cells |
70
|
|
|
* |
71
|
|
|
* @throws PathException When an invalid path is given |
72
|
|
|
*/ |
73
|
|
|
public Path<C> decode(String encoded, C start) throws PathException { |
74
|
1 |
|
if (encoded.length() % 3 != 0) { |
75
|
1 |
|
throw new PathException("Invalid path : bad length"); |
76
|
|
|
} |
77
|
|
|
|
78
|
1 |
|
final Path<C> path = new Path<>(this); |
79
|
|
|
|
80
|
|
|
// Add the start cell on the path |
81
|
1 |
|
if (start != null) { |
82
|
1 |
|
path.add(new PathStep<>(start, Direction.EAST)); |
83
|
|
|
} |
84
|
|
|
|
85
|
1 |
|
for (int i = 0; i < encoded.length(); i += 3) { |
86
|
1 |
|
final Direction direction = Direction.byChar(encoded.charAt(i)); |
87
|
1 |
|
final int cell = (Base64.ord(encoded.charAt(i + 1)) & 15) << 6 | Base64.ord(encoded.charAt(i + 2)); |
88
|
|
|
|
89
|
1 |
|
if (cell >= map.size()) { |
90
|
1 |
|
throw new PathException("Invalid cell number"); |
91
|
|
|
} |
92
|
|
|
|
93
|
|
|
// First cell of the path, without a start cell : add it to the path |
94
|
1 |
|
if (path.isEmpty()) { |
95
|
1 |
|
path.add(new PathStep<>(map.get(cell), Direction.EAST)); |
96
|
1 |
|
continue; |
97
|
|
|
} |
98
|
|
|
|
99
|
1 |
|
expandRectilinearMove(path, path.target(), map.get(cell), direction); |
100
|
|
|
} |
101
|
|
|
|
102
|
1 |
|
return path; |
103
|
|
|
} |
104
|
|
|
|
105
|
|
|
/** |
106
|
|
|
* Decode compressed path without a start cell |
107
|
|
|
* |
108
|
|
|
* @param encoded The encoded path. Must contains the start cell |
109
|
|
|
|
110
|
|
|
* @return The path, with list of cells |
111
|
|
|
* |
112
|
|
|
* @throws PathException When an invalid path is given |
113
|
|
|
*/ |
114
|
|
|
public Path<C> decode(String encoded) throws PathException { |
115
|
1 |
|
return decode(encoded, null); |
116
|
|
|
} |
117
|
|
|
|
118
|
|
|
/** |
119
|
|
|
* Encode the computed path, including the start cell |
120
|
|
|
* To decode this path, the start cell should not be provided on the decode method |
121
|
|
|
* |
122
|
|
|
* This method should be used by server to send a path to the client |
123
|
|
|
* |
124
|
|
|
* <code> |
125
|
|
|
* String encoded = encoder.encodeWithStartCell(myPath); |
126
|
|
|
* Path decoded = encoder.decode(encoded); |
127
|
|
|
* </code> |
128
|
|
|
* |
129
|
|
|
* @param path The path to encode |
130
|
|
|
* |
131
|
|
|
* @return The encoded path |
132
|
|
|
*/ |
133
|
|
|
public String encodeWithStartCell(Path<C> path) { |
134
|
1 |
|
return encode(path, true); |
135
|
|
|
} |
136
|
|
|
|
137
|
|
|
/** |
138
|
|
|
* Encode the computed path, without the start cell |
139
|
|
|
* To decode this path, the start cell must be provided on the decode method |
140
|
|
|
* |
141
|
|
|
* This method should be used by the client to send a path to the server |
142
|
|
|
* |
143
|
|
|
* <code> |
144
|
|
|
* String encoded = encoder.encode(myPath); |
145
|
|
|
* Path decoded = encoder.decode(encoded, startCell); |
146
|
|
|
* </code> |
147
|
|
|
* |
148
|
|
|
* @param path The path to encode |
149
|
|
|
* |
150
|
|
|
* @return The encoded path |
151
|
|
|
* |
152
|
|
|
* @see Pathfinder#addFirstCell(boolean) Set to false to generate a path without the start cell |
153
|
|
|
*/ |
154
|
|
|
public String encode(Path<C> path) { |
155
|
1 |
|
return encode(path, false); |
156
|
|
|
} |
157
|
|
|
|
158
|
|
|
/** |
159
|
|
|
* Get the pathfinder related to this decoder |
160
|
|
|
* |
161
|
|
|
* @return The pathfinder instance |
162
|
|
|
*/ |
163
|
|
|
public Pathfinder<C> pathfinder() { |
164
|
1 |
|
return new Pathfinder<>(this); |
165
|
|
|
} |
166
|
|
|
|
167
|
|
|
private void expandRectilinearMove(Path<C> path, C start, C target, Direction direction) throws PathException { |
168
|
1 |
|
int stepsLimit = 2 * map.dimensions().width() + 1; |
169
|
|
|
|
170
|
1 |
|
while (!start.equals(target)) { |
171
|
1 |
|
start = nextCellByDirection(start, direction).orElseThrow(() -> new PathException("Invalid cell number")); |
172
|
1 |
|
path.add(new PathStep<>(start, direction)); |
173
|
|
|
|
174
|
1 |
|
if (--stepsLimit < 0) { |
175
|
1 |
|
throw new PathException("Invalid path : bad direction"); |
176
|
|
|
} |
177
|
|
|
} |
178
|
1 |
|
} |
179
|
|
|
|
180
|
|
|
/** |
181
|
|
|
* Encode the computed path |
182
|
|
|
* |
183
|
|
|
* @param path The path to encode |
184
|
|
|
* @param includeStartCell Does the encoded path should contains the start cell or not ? |
185
|
|
|
* |
186
|
|
|
* @return The encoded path |
187
|
|
|
*/ |
188
|
|
|
private String encode(Path<C> path, boolean includeStartCell) { |
189
|
1 |
|
final StringBuilder encoded = new StringBuilder(path.size() * 3); |
190
|
|
|
|
191
|
|
|
// The start cell must be added to path without compression |
192
|
1 |
|
if (includeStartCell) { |
193
|
1 |
|
encoded |
194
|
1 |
|
.append(Direction.EAST.toChar()) |
195
|
1 |
|
.append(Base64.encode(path.get(0).cell().id(), 2)) |
196
|
|
|
; |
197
|
|
|
} |
198
|
|
|
|
199
|
|
|
// Start the path at step 1 : the start cell is added before |
200
|
1 |
|
for (int i = (includeStartCell ? 1 : 0); i < path.size(); ++i) { |
201
|
1 |
|
final PathStep<C> step = path.get(i); |
202
|
|
|
|
203
|
1 |
|
encoded.append(step.direction().toChar()); |
204
|
|
|
|
205
|
|
|
// Skip cells on same direction |
206
|
1 |
|
while (i + 1 < path.size() && path.get(i + 1).direction() == step.direction()) { |
207
|
1 |
|
++i; |
|
|
|
|
208
|
|
|
} |
209
|
|
|
|
210
|
1 |
|
encoded.append(Base64.encode(path.get(i).cell().id(), 2)); |
211
|
|
|
} |
212
|
|
|
|
213
|
1 |
|
return encoded.toString(); |
214
|
|
|
} |
215
|
|
|
} |
216
|
|
|
|