SCI32: Change plane and screen item sorting algorithm

SSCI's last resort comparison here was to compare the object IDs
of planes & screen items, but this randomly breaks (at least) the
"you have died" dialog at the end of Phant1, and text & buttons
in Hoyle5, even in SSCI itself.

This commit changes last resort comparison to use a monotonically
increasing ID instead, which keeps objects with identical priority
& z-index in creation order when compared.

Fixes Trac#9585.

4 files changed, 73 insertions, 6 deletions

diff --git a/engines/sci/graphics/plane32.cpp b/engines/sci/graphics/plane32.cpp
index f56df4dced..46622261f5 100644
--- a/engines/sci/graphics/plane32.cpp
+++ b/engines/sci/graphics/plane32.cpp
@@ -44,8 +44,10 @@ void DrawList::add(ScreenItem *screenItem, const Common::Rect &rect) {
 #pragma mark -
 #pragma mark Plane
 uint16 Plane::_nextObjectId = 20000;
+uint32 Plane::_nextCreationId = 0;
 
 Plane::Plane(const Common::Rect &gameRect, PlanePictureCodes pictureId) :
+_creationId(_nextCreationId++),
 _pictureId(pictureId),
 _mirrored(false),
 _type(kPlaneTypeColored),
@@ -65,6 +67,7 @@ _gameRect(gameRect) {
 }
 
 Plane::Plane(reg_t object) :
+_creationId(_nextCreationId++),
 _type(kPlaneTypeColored),
 _priorityChanged(false),
 _object(object),
@@ -94,6 +97,7 @@ _moved(0) {
 }
 
 Plane::Plane(const Plane &other) :
+_creationId(other._creationId),
 _pictureId(other._pictureId),
 _mirrored(other._mirrored),
 _type(other._type),
@@ -106,6 +110,7 @@ _screenRect(other._screenRect),
 _screenItemList(other._screenItemList) {}
 
 void Plane::operator=(const Plane &other) {
+	_creationId = other._creationId;
 	_gameRect = other._gameRect;
 	_planeRect = other._planeRect;
 	_vanishingPoint = other._vanishingPoint;
@@ -120,6 +125,7 @@ void Plane::operator=(const Plane &other) {
 
 void Plane::init() {
 	_nextObjectId = 20000;
+	_nextCreationId = 0;
 }
 
 void Plane::convertGameRectToPlaneRect() {
@@ -144,11 +150,12 @@ void Plane::printDebugInfo(Console *con) const {
 		name = g_sci->getEngineState()->_segMan->getObjectName(_object);
 	}
 
-	con->debugPrintf("%04x:%04x (%s): type %d, prio %d, pic %d, mirror %d, back %d\n",
+	con->debugPrintf("%04x:%04x (%s): type %d, prio %d, ins %u, pic %d, mirror %d, back %d\n",
 		PRINT_REG(_object),
 		name.c_str(),
 		_type,
 		_priority,
+		_creationId,
 		_pictureId,
 		_mirrored,
 		_back
@@ -508,7 +515,7 @@ void Plane::calcLists(Plane &visiblePlane, const PlaneList &planeList, DrawList
 					const ScreenItem *drawnItem = drawListEntry->screenItem;
 
 					if (
-						(newItem->_priority > drawnItem->_priority || (newItem->_priority == drawnItem->_priority && newItem->_object > drawnItem->_object)) &&
+						(newItem->_priority > drawnItem->_priority || (newItem->_priority == drawnItem->_priority && newItem->_creationId > drawnItem->_creationId)) &&
 						drawListEntry->rect.intersects(newItem->_screenRect)
 					) {
 						mergeToDrawList(j, drawListEntry->rect.findIntersectingRect(newItem->_screenRect), drawList);
diff --git a/engines/sci/graphics/plane32.h b/engines/sci/graphics/plane32.h
index 964d20ca12..a34df1cc1a 100644
--- a/engines/sci/graphics/plane32.h
+++ b/engines/sci/graphics/plane32.h
@@ -110,6 +110,20 @@ private:
 	static uint16 _nextObjectId;
 
 	/**
+	 * A serial used to identify the creation order of
+	 * planes, to ensure a stable sort order for planes
+	 * with identical priorities.
+	 */
+	static uint32 _nextCreationId;
+
+	/**
+	 * The creation order number, which ensures a stable
+	 * sort when planes with identical priorities are added
+	 * to the plane list.
+	 */
+	uint32 _creationId;
+
+	/**
 	 * For planes that are used to render picture data, the
 	 * resource ID of the picture to be displayed. This
 	 * value may also be one of the special
@@ -261,7 +275,9 @@ public:
 		}
 
 		if (_priority == other._priority) {
-			return _object < other._object;
+			// This is different than SSCI; see ScreenItem::operator< for an
+			// explanation
+			return _creationId < other._creationId;
 		}
 
 		return false;
diff --git a/engines/sci/graphics/screen_item32.cpp b/engines/sci/graphics/screen_item32.cpp
index 9b0d390cc3..a70f25fd6b 100644
--- a/engines/sci/graphics/screen_item32.cpp
+++ b/engines/sci/graphics/screen_item32.cpp
@@ -34,8 +34,10 @@ namespace Sci {
 #pragma mark ScreenItem
 
 uint16 ScreenItem::_nextObjectId = 20000;
+uint32 ScreenItem::_nextCreationId = 0;
 
 ScreenItem::ScreenItem(const reg_t object) :
+_creationId(_nextCreationId++),
 _celObj(nullptr),
 _object(object),
 _pictureId(-1),
@@ -51,6 +53,7 @@ _drawBlackLines(false) {
 }
 
 ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo) :
+_creationId(_nextCreationId++),
 _plane(plane),
 _useInsetRect(false),
 _z(0),
@@ -67,6 +70,7 @@ _mirrorX(false),
 _drawBlackLines(false) {}
 
 ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo, const Common::Rect &rect) :
+_creationId(_nextCreationId++),
 _plane(plane),
 _useInsetRect(false),
 _z(0),
@@ -87,6 +91,7 @@ _drawBlackLines(false) {
 }
 
 ScreenItem::ScreenItem(const reg_t plane, const CelInfo32 &celInfo, const Common::Point &position, const ScaleInfo &scaleInfo) :
+_creationId(_nextCreationId++),
 _plane(plane),
 _scale(scaleInfo),
 _useInsetRect(false),
@@ -104,6 +109,7 @@ _mirrorX(false),
 _drawBlackLines(false) {}
 
 ScreenItem::ScreenItem(const ScreenItem &other) :
+_creationId(other._creationId),
 _plane(other._plane),
 _scale(other._scale),
 _useInsetRect(other._useInsetRect),
@@ -131,6 +137,7 @@ void ScreenItem::operator=(const ScreenItem &other) {
 		_celObj = nullptr;
 	}
 
+	_creationId = other._creationId;
 	_screenRect = other._screenRect;
 	_mirrorX = other._mirrorX;
 	_useInsetRect = other._useInsetRect;
@@ -148,6 +155,7 @@ ScreenItem::~ScreenItem() {
 
 void ScreenItem::init() {
 	_nextObjectId = 20000;
+	_nextCreationId = 0;
 }
 
 void ScreenItem::setFromObject(SegManager *segMan, const reg_t object, const bool updateCel, const bool updateBitmap) {
@@ -476,10 +484,11 @@ CelObj &ScreenItem::getCelObj() const {
 }
 
 void ScreenItem::printDebugInfo(Console *con) const {
-	con->debugPrintf("%04x:%04x (%s), prio %d, x %d, y %d, z: %d, scaledX: %d, scaledY: %d flags: %d\n",
+	con->debugPrintf("%04x:%04x (%s), prio %d, ins %u, x %d, y %d, z: %d, scaledX: %d, scaledY: %d flags: %d\n",
 		_object.getSegment(), _object.getOffset(),
 		g_sci->getEngineState()->_segMan->getObjectName(_object),
 		_priority,
+		_creationId,
 		_position.x,
 		_position.y,
 		_z,
diff --git a/engines/sci/graphics/screen_item32.h b/engines/sci/graphics/screen_item32.h
index 009b608f18..c2c4e43358 100644
--- a/engines/sci/graphics/screen_item32.h
+++ b/engines/sci/graphics/screen_item32.h
@@ -61,6 +61,13 @@ private:
 	 */
 	static uint16 _nextObjectId;
 
+	/**
+	 * A serial used to identify the creation order of
+	 * screen items, to ensure a stable sort order for
+	 * screen items with identical priorities and z-indexes.
+	 */
+	static uint32 _nextCreationId;
+
 public:
 	/**
 	 * The parent plane of this screen item.
@@ -120,6 +127,13 @@ private:
 
 public:
 	/**
+	 * The creation order number, which ensures a stable
+	 * sort when screen items with identical priorities and
+	 * z-indexes are added to the screen item list.
+	 */
+	uint32 _creationId;
+
+	/**
 	 * A descriptor for the cel object represented by the
 	 * screen item.
 	 */
@@ -242,7 +256,26 @@ public:
 			}
 
 			if (_position.y + _z == other._position.y + other._z) {
-				return _object < other._object;
+				// SSCI's last resort comparison here is to compare the _object
+				// IDs, but this is wrong and randomly breaks (at least):
+				//
+				// (1) the death dialog at the end of Phant1, where the ID of
+				//     the text is often higher than the ID of the border;
+				// (2) text-based buttons and dialogues in Hoyle5, where the ID
+				//     of the text is often lower than the ID of the
+				//     button/dialogue background.
+				//
+				// This occurs because object IDs (in both ScummVM and SSCI) are
+				// reused, so objects created later may receive a lower ID,
+				// which makes them sort lower when the programmer intended them
+				// to sort higher.
+				//
+				// To fix this problem, we give each ScreenItem a monotonically
+				// increasing insertion ID at construction time, and compare
+				// these insertion IDs instead. They are more stable and cause
+				// objects with identical priority and z-index to be rendered in
+				// the order that they were created.
+				return _creationId < other._creationId;
 			}
 		}
 
@@ -260,7 +293,9 @@ public:
 			}
 
 			if (_position.y + _z == other._position.y + other._z) {
-				return _object > other._object;
+				// This is different than SSCI; see ScreenItem::operator< for an
+				// explanation
+				return _creationId > other._creationId;
 			}
 		}