1 /* ScummVM - Graphic Adventure Engine
2 *
3 * ScummVM is the legal property of its developers, whose names
4 * are too numerous to list here. Please refer to the COPYRIGHT
5 * file distributed with this source distribution.
6 *
7 * This program is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU General Public License
9 * as published by the Free Software Foundation; either version 2
10 * of the License, or (at your option) any later version.
11 *
12 * This program is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU General Public License
18 * along with this program; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
20 *
21 */
22
23 #include "ultima/ultima8/misc/pent_include.h"
24 #include "ultima/ultima8/world/item_sorter.h"
25 #include "ultima/ultima8/world/item.h"
26 #include "ultima/ultima8/graphics/shape.h"
27 #include "ultima/ultima8/graphics/shape_frame.h"
28 #include "ultima/ultima8/graphics/main_shape_archive.h"
29 #include "ultima/ultima8/graphics/render_surface.h"
30 #include "ultima/ultima8/misc/rect.h"
31 #include "ultima/ultima8/games/game_data.h"
32 #include "ultima/ultima8/ultima8.h"
33
34 // temp
35 #include "ultima/ultima8/world/actors/weapon_overlay.h"
36 #include "ultima/ultima8/world/actors/main_actor.h"
37 #include "ultima/ultima8/world/get_object.h"
38 // --
39
40 #include "ultima/ultima8/world/sort_item.h"
41
42 namespace Ultima {
43 namespace Ultima8 {
44
ItemSorter()45 ItemSorter::ItemSorter() :
46 _shapes(nullptr), _surf(nullptr), _items(nullptr), _itemsTail(nullptr),
47 _itemsUnused(nullptr), _sortLimit(0), _camSx(0), _camSy(0), _orderCounter(0) {
48 int i = 2048;
49 while (i--) _itemsUnused = new SortItem(_itemsUnused);
50 }
51
~ItemSorter()52 ItemSorter::~ItemSorter() {
53 //
54 if (_itemsTail) {
55 _itemsTail->_next = _itemsUnused;
56 _itemsUnused = _items;
57 }
58 _items = nullptr;
59 _itemsTail = nullptr;
60
61 while (_itemsUnused) {
62 SortItem *_next = _itemsUnused->_next;
63 delete _itemsUnused;
64 _itemsUnused = _next;
65 }
66
67 delete [] _items;
68 }
69
BeginDisplayList(RenderSurface * rs,int32 camx,int32 camy,int32 camz)70 void ItemSorter::BeginDisplayList(RenderSurface *rs,
71 int32 camx, int32 camy, int32 camz) {
72 // Get the _shapes, if required
73 if (!_shapes) _shapes = GameData::get_instance()->getMainShapes();
74
75 //
76 if (_itemsTail) {
77 _itemsTail->_next = _itemsUnused;
78 _itemsUnused = _items;
79 }
80 _items = nullptr;
81 _itemsTail = nullptr;
82
83 // Set the RenderSurface, and reset the item list
84 _surf = rs;
85 _orderCounter = 0;
86
87 // Screenspace bounding box bottom x coord (RNB x coord)
88 _camSx = (camx - camy) / 4;
89 // Screenspace bounding box bottom extent (RNB y coord)
90 _camSy = (camx + camy) / 8 - camz;
91 }
92
AddItem(int32 x,int32 y,int32 z,uint32 shapeNum,uint32 frame_num,uint32 flags,uint32 ext_flags,uint16 itemNum)93 void ItemSorter::AddItem(int32 x, int32 y, int32 z, uint32 shapeNum, uint32 frame_num, uint32 flags, uint32 ext_flags, uint16 itemNum) {
94
95 // First thing, get a SortItem to use (first of unused)
96 if (!_itemsUnused)
97 _itemsUnused = new SortItem(0);
98 SortItem *si = _itemsUnused;
99
100 si->_itemNum = itemNum;
101 si->_shape = _shapes->getShape(shapeNum);
102 si->_shapeNum = shapeNum;
103 si->_frame = frame_num;
104 const ShapeFrame *_frame = si->_shape ? si->_shape->getFrame(si->_frame) : nullptr;
105 if (!_frame) {
106 perr << "Invalid shape: " << si->_shapeNum << "," << si->_frame << Std::endl;
107 return;
108 }
109
110 si->_flags = flags;
111 si->_extFlags = ext_flags;
112
113 const ShapeInfo *info = _shapes->getShapeInfo(shapeNum);
114 // Dimensions
115 int32 xd, yd, zd;
116 info->getFootpadWorld(xd, yd, zd, flags & Item::FLG_FLIPPED);
117
118 // Worldspace bounding box
119 si->_x = x;
120 si->_y = y;
121 si->_z = z;
122 si->_xLeft = si->_x - xd;
123 si->_yFar = si->_y - yd;
124 si->_zTop = si->_z + zd;
125
126 // Screenspace bounding box left extent (LNT x coord)
127 si->_sxLeft = si->_xLeft / 4 - si->_y / 4 - _camSx;
128 // Screenspace bounding box right extent (RFT x coord)
129 si->_sxRight = si->_x / 4 - si->_yFar / 4 - _camSx;
130
131 // Screenspace bounding box top x coord (LFT x coord)
132 si->_sxTop = si->_xLeft / 4 - si->_yFar / 4 - _camSx;
133 // Screenspace bounding box top extent (LFT y coord)
134 si->_syTop = si->_xLeft / 8 + si->_yFar / 8 - si->_zTop - _camSy;
135
136 // Screenspace bounding box bottom x coord (RNB x coord)
137 si->_sxBot = si->_x / 4 - si->_y / 4 - _camSx;
138 // Screenspace bounding box bottom extent (RNB y coord)
139 si->_syBot = si->_x / 8 + si->_y / 8 - si->_z - _camSy;
140
141 // Real Screenspace coords
142 si->_sx = si->_sxBot - _frame->_xoff; // Left
143 si->_sy = si->_syBot - _frame->_yoff; // Top
144 si->_sx2 = si->_sx + _frame->_width; // Right
145 si->_sy2 = si->_sy + _frame->_height; // Bottom
146
147 // Do Clipping here
148 int16 clipped = _surf->CheckClipped(Rect(si->_sx, si->_sy, si->_sx + _frame->_width, si->_sy + _frame->_height));
149 if (clipped < 0)
150 // Clipped away entirely - don't add to the list.
151 return;
152
153 si->_clipped = (clipped != 0);
154
155 // These help out with sorting. We calc them now, so it will be faster
156 si->_fbigsq = (xd == 128 && yd == 128) || (xd == 256 && yd == 256) || (xd == 512 && yd == 512);
157 si->_flat = zd == 0;
158
159 si->_draw = info->is_draw();
160 si->_solid = info->is_solid();
161 si->_occl = info->is_occl() && !(si->_flags & Item::FLG_INVISIBLE) &&
162 !(si->_extFlags & Item::EXT_TRANSPARENT);
163 si->_roof = info->is_roof();
164 si->_noisy = info->is_noisy();
165 si->_anim = info->_animType != 0;
166 si->_trans = info->is_translucent();
167 si->_fixed = info->is_fixed();
168 si->_land = info->is_land();
169 if (GAME_IS_CRUSADER) {
170 si->_sprite = si->_extFlags & Item::EXT_SPRITE;
171 si->_invitem = info->is_invitem();
172 }
173
174 si->_occluded = false;
175 si->_order = -1;
176
177 // We will clear all the vector memory
178 // Stictly speaking the vector will sort of leak memory, since they
179 // are never deleted
180 si->_depends.clear();
181
182 // Iterate the list and compare _shapes
183
184 // Ok,
185 SortItem *addpoint = nullptr;
186 for (SortItem *si2 = _items; si2 != nullptr; si2 = si2->_next) {
187 // Get the insert point... which is before the first item that has higher z than us
188 if (!addpoint && si->ListLessThan(si2))
189 addpoint = si2;
190
191 // Doesn't overlap
192 if (si2->_occluded || !si->overlap(*si2))
193 continue;
194
195 // Attempt to find which is infront
196 if (si->below(*si2)) {
197 // si2 occludes si (us)
198 if (si2->_occl && si2->occludes(*si)) {
199 // No need to do any more checks, this isn't visible
200 si->_occluded = true;
201 break;
202 }
203
204 // si1 is behind si2, so add it to si2's dependency list
205 si2->_depends.insert_sorted(si);
206 } else {
207 // ss occludes si2. Sadly, we can't remove it from the list.
208 if (si->_occl && si->occludes(*si2))
209 si2->_occluded = true;
210 // si2 is behind si1, so add it to si1's dependency list
211 else
212 si->_depends.push_back(si2);
213 }
214 }
215
216 // Add it to the list
217 _itemsUnused = _itemsUnused->_next;
218
219 // have a position
220 //addpoint = 0;
221 if (addpoint) {
222 si->_next = addpoint;
223 si->_prev = addpoint->_prev;
224 addpoint->_prev = si;
225 if (si->_prev)
226 si->_prev->_next = si;
227 else
228 _items = si;
229 }
230 // Add it to the end of the list
231 else {
232 if (_itemsTail)
233 _itemsTail->_next = si;
234 if (!_items)
235 _items = si;
236 si->_next = nullptr;
237 si->_prev = _itemsTail;
238 _itemsTail = si;
239 }
240 }
241
AddItem(const Item * add)242 void ItemSorter::AddItem(const Item *add) {
243 int32 x, y, z;
244 add->getLerped(x, y, z);
245 AddItem(x, y, z, add->getShape(), add->getFrame(),
246 add->getFlags(), add->getExtFlags(), add->getObjId());
247 }
248
249 SortItem *_prev = 0;
250
PaintDisplayList(bool item_highlight)251 void ItemSorter::PaintDisplayList(bool item_highlight) {
252 _prev = nullptr;
253 SortItem *it = _items;
254 SortItem *end = nullptr;
255 _orderCounter = 0; // Reset the _orderCounter
256 while (it != end) {
257 if (it->_order == -1) if (PaintSortItem(it)) return;
258 it = it->_next;
259 }
260
261 // Item highlighting. We redraw each 'item' transparent
262 if (item_highlight) {
263 it = _items;
264 while (it != end) {
265 if (!(it->_flags & (Item::FLG_DISPOSABLE | Item::FLG_FAST_ONLY)) && !it->_fixed) {
266 _surf->PaintHighlightInvis(it->_shape,
267 it->_frame,
268 it->_sxBot,
269 it->_syBot,
270 it->_trans,
271 (it->_flags & Item::FLG_FLIPPED) != 0, 0x1f00ffff);
272 }
273
274 it = it->_next;
275 }
276
277 }
278 }
279
280 /**
281 * Recursively paint this item and all its dependencies.
282 * Returns true if recursion should stop.
283 */
PaintSortItem(SortItem * si)284 bool ItemSorter::PaintSortItem(SortItem *si) {
285 // Don't paint this, or dependencies (yet) if occluded
286 if (si->_occluded)
287 return false;
288
289 // Resursion detection
290 si->_order = -2;
291
292 // Iterate through our dependancies, and paint them, if possible
293 SortItem::DependsList::iterator it = si->_depends.begin();
294 SortItem::DependsList::iterator end = si->_depends.end();
295 while (it != end) {
296 if ((*it)->_order == -2) {
297 //warning("cycle in paint dependency graph %d -> %d -> ... -> %d",
298 // si->_shapeNum, (*it)->_shapeNum, si->_shapeNum);
299 break;
300 }
301 else if ((*it)->_order == -1) {
302 if (PaintSortItem((*it)))
303 return true;
304 }
305 ++it;
306 }
307
308 // Set our painting _order
309 si->_order = _orderCounter;
310 _orderCounter++;
311
312 // Now paint us!
313
314 // if (wire) si->info->draw_box_back(s, dispx, dispy, 255);
315
316 if (si->_extFlags & Item::EXT_HIGHLIGHT && si->_extFlags & Item::EXT_TRANSPARENT)
317 _surf->PaintHighlightInvis(si->_shape, si->_frame, si->_sxBot, si->_syBot, si->_trans, (si->_flags & Item::FLG_FLIPPED) != 0, 0x7F00007F);
318 if (si->_extFlags & Item::EXT_HIGHLIGHT)
319 _surf->PaintHighlight(si->_shape, si->_frame, si->_sxBot, si->_syBot, si->_trans, (si->_flags & Item::FLG_FLIPPED) != 0, 0x7F00007F);
320 else if (si->_extFlags & Item::EXT_TRANSPARENT)
321 _surf->PaintInvisible(si->_shape, si->_frame, si->_sxBot, si->_syBot, si->_trans, (si->_flags & Item::FLG_FLIPPED) != 0);
322 else if (si->_flags & Item::FLG_FLIPPED)
323 _surf->PaintMirrored(si->_shape, si->_frame, si->_sxBot, si->_syBot, si->_trans);
324 else if (si->_trans)
325 _surf->PaintTranslucent(si->_shape, si->_frame, si->_sxBot, si->_syBot);
326 else if (!si->_clipped)
327 _surf->PaintNoClip(si->_shape, si->_frame, si->_sxBot, si->_syBot);
328 else
329 _surf->Paint(si->_shape, si->_frame, si->_sxBot, si->_syBot);
330
331 // if (wire) si->info->draw_box_front(s, dispx, dispy, 255);
332
333 // weapon overlay
334 // FIXME: use highlight/invisibility, also add to Trace() ?
335 if (si->_shapeNum == 1 && si->_itemNum == 1) {
336 MainActor *av = getMainActor();
337 const WeaponOverlayFrame *wo_frame = nullptr;
338 uint32 wo_shapenum;
339 av->getWeaponOverlay(wo_frame, wo_shapenum);
340 if (wo_frame) {
341 const Shape *wo_shape = GameData::get_instance()->getMainShapes()->getShape(wo_shapenum);
342 _surf->Paint(wo_shape, wo_frame->_frame,
343 si->_sxBot + wo_frame->_xOff,
344 si->_syBot + wo_frame->_yOff);
345 }
346 }
347
348 if (_sortLimit) {
349 if (_orderCounter == _sortLimit) {
350 static uint32 previt = 0;
351 if (!previt || previt != si->_itemNum) {
352 previt = si->_itemNum;
353 pout << "SortItem: " << *si << Std::endl;
354 if (_prev && si->overlap(_prev)) {
355 pout << "Overlaps: " << *_prev << Std::endl;
356 }
357 }
358 return true;
359 }
360 _prev = si;
361 }
362
363 return false;
364 }
365
NullPaintSortItem(SortItem * si)366 bool ItemSorter::NullPaintSortItem(SortItem *si) {
367 // Don't paint this, or dependencies if occluded
368 if (si->_occluded) return false;
369
370 // Resursion, detection
371 si->_order = -2;
372
373 // Iterate through our dependancies, and paint them, if possible
374 SortItem::DependsList::iterator it = si->_depends.begin();
375 SortItem::DependsList::iterator end = si->_depends.end();
376 while (it != end) {
377 // Well, it can't. Implies recursive sorting. Can happen though so
378 // you had best leave this commented out
379 //if ((*it)->_order == -2) CANT_HAPPEN_MSG("Recursive item sorting");
380
381 if ((*it)->_order == -1) if (NullPaintSortItem((*it))) return true;
382
383 ++it;
384 }
385
386 // Set our painting/sorting _order
387 si->_order = _orderCounter;
388 _orderCounter++;
389
390 return false;
391 }
392
Trace(int32 x,int32 y,HitFace * face,bool item_highlight)393 uint16 ItemSorter::Trace(int32 x, int32 y, HitFace *face, bool item_highlight) {
394 SortItem *it;
395 SortItem *selected;
396
397 if (!_orderCounter) { // If no _orderCounter we need to sort the _items
398 it = _items;
399 _orderCounter = 0; // Reset the _orderCounter
400 while (it != nullptr) {
401 if (it->_order == -1) if (NullPaintSortItem(it)) break;
402
403 it = it->_next;
404 }
405 }
406
407 // Firstly, we check for highlighted _items
408 selected = nullptr;
409
410 if (item_highlight) {
411 selected = nullptr;
412
413 for (it = _itemsTail; it != nullptr; it = it->_prev) {
414 if (!(it->_flags & (Item::FLG_DISPOSABLE | Item::FLG_FAST_ONLY)) && !it->_fixed) {
415
416 if (!it->_itemNum) continue;
417
418 // Doesn't Overlap
419 if (x < it->_sx || x >= it->_sx2 || y < it->_sy || y >= it->_sy2) continue;
420
421 // Now check the _frame itself
422 const ShapeFrame *_frame = it->_shape->getFrame(it->_frame);
423 assert(_frame); // invalid frames shouldn't have been added to the list
424
425 // Nope, doesn't have a point
426 if (it->_flags & Item::FLG_FLIPPED) {
427 if (!_frame->hasPoint(it->_sxBot - x, y - it->_syBot)) continue;
428 } else {
429 if (!_frame->hasPoint(x - it->_sxBot, y - it->_syBot)) continue;
430 }
431
432 // Ok now check against selected
433 selected = it;
434 }
435 }
436
437 }
438
439 // Ok, this is all pretty simple. We iterate all the _items.
440 // We then check to see if the item has a point where the trace goes.
441 // Finally we then set the selected SortItem if it's '_order' is highest
442
443 if (!selected) for (it = _items; it != nullptr; it = it->_next) {
444 if (!it->_itemNum) continue;
445
446 // Doesn't Overlap
447 if (x < it->_sx || x >= it->_sx2 || y < it->_sy || y >= it->_sy2) continue;
448
449 // Now check the _frame itself
450 const ShapeFrame *_frame = it->_shape->getFrame(it->_frame);
451 assert(_frame); // invalid frames shouldn't have been added to the list
452
453 // Nope, doesn't have a point
454 if (it->_flags & Item::FLG_FLIPPED) {
455 if (!_frame->hasPoint(it->_sxBot - x, y - it->_syBot)) continue;
456 } else {
457 if (!_frame->hasPoint(x - it->_sxBot, y - it->_syBot)) continue;
458 }
459
460 // Ok now check against selected
461 if (!selected || (it->_order > selected->_order)) selected = it;
462 }
463
464 if (selected) {
465
466 if (face) {
467 // shortcut for zero-height _items
468 if (selected->_zTop == selected->_z) {
469 *face = Z_FACE;
470 } else {
471 // determine face that was hit
472
473 // RNT coordinates
474 int32 RNTx = selected->_sxBot;
475 int32 RNTy = selected->_syBot - selected->_zTop + selected->_z;
476
477 /*
478 Bounding Box layout (top part)
479
480 1
481 / \
482 / \ 1 = Left Far Top LFT --+
483 2 Z-face 3 2 = Left Near Top LNT -++
484 | \ / | 3 = Right Far Top RFT +-+
485 | \ / | 4 = Right Near Top RNT +++
486 | Y 4 X |
487 |face |face |
488
489 */
490
491 if (2 * (y - RNTy) <= (x - RNTx) && // if above/on line 4-3
492 2 * (y - RNTy) < (RNTx - x)) // and above/on line 4-2
493 *face = Z_FACE;
494 else if (x > RNTx)
495 *face = X_FACE;
496 else
497 *face = Y_FACE;
498 }
499 }
500
501 return selected->_itemNum;
502 }
503
504 return 0;
505 }
506
IncSortLimit(int count)507 void ItemSorter::IncSortLimit(int count) {
508 _sortLimit += count;
509 if (_sortLimit < 0)
510 _sortLimit = 0;
511 }
512
513 } // End of namespace Ultima8
514 } // End of namespace Ultima
515