A deep dive into Pixel Dungeon's long-standing spawning issues

[gigalh128]

The way Shattered Pixel Dungeon handles placing characters in the dungeon is inherently flawed, in a way that allows for fascinating exploits and causes many bugs. This is not Shattered’s fault: the issue stems all the way back from how Vanilla PD handled this task -- assuming open space exists. It would be great to see these fixed in Shattered because a lot of mods are also inheriting these same bugs!

There are two main issues: invalid infinite loops and short sighted space availability checks.

Code issue examples

Invalid infinite loop

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/RegularLevel.java

Lines 558 to 574 in 4f32d90

	public int fallCell( boolean fallIntoPit ) {
	if (fallIntoPit) {
	for (Room room : rooms) {
	if (room instanceof PitRoom) {
	int result;
	do {
	result = pointToCell(room.random());
	} while (traps.get(result) != null
	|| findMob(result) != null
	|| heaps.get(result) != null);
	return result;
	}
	}
	}
	return super.fallCell( false );
	}

If you drop an item on each cell in a pit room, then jump into it, the game will infinitely loop. Alternatively, you can just throw a stone of flock into the room. Interestingly, you can use this to get a death by falling on floor 1. For actions like these, there needs to be some kind of failsafe implemented because it's within the player's control to cause failures.

Short-Sighted Space Availability Check

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/items/spells/BeaconOfReturning.java

Lines 122 to 131 in 4f32d90

	moving.pos = returnPos;
	for(int i : PathFinder.NEIGHBOURS8){
	if (Actor.findChar(moving.pos+i) == null
	&& Dungeon.level.passable[moving.pos + i]
	&& (!Char.hasProp(moving, Char.Property.LARGE) || Dungeon.level.openSpace[moving.pos + i])){
	moving.pos += i;
	moving.sprite.point(moving.sprite.worldToCamera(moving.pos));
	break;
	}
	}

This code makes the beacon of returning hands down one of the best items. Because it doesn't do anything special if your original location + all 8 neighbors fail, it gives you an easy way to spawn inside of your enemies and make use of char stacking properties. Of course, this is probably not the intended behavior, so the game needs to also check if all cases fail and act accordingly.

Locations and Descriptions of Failure

Please feel free to double check these things. If I can't find something in the code, I'll do my best to describe how it happens with video footage.
Many of these scenarios can be done in game with enough ring of wealth/wand of regrowth/blooming or lucky weapon patience. I could also be missing some areas.

Invalid Infinite Loops

Level RandomRespawnCell Methods

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/Level.java

  Lines 689 to 698 in 4f32d90

  	public int randomRespawnCell( Char ch ) {
  	int cell;
  	do {
  	cell = Random.Int( length() );
  	} while ((Dungeon.level == this && heroFOV[cell])
  	|| !passable[cell]
  	|| (Char.hasProp(ch, Char.Property.LARGE) && !openSpace[cell])
  	|| Actor.findChar( cell ) != null);
  	return cell;
  	}

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/RegularLevel.java

  Lines 272 to 294 in 4f32d90

  	while (true) {
  	if (++count > 30) {
  	return -1;
  	}
  	Room room = randomRoom( StandardRoom.class );
  	if (room == null || room == roomEntrance) {
  	continue;
  	}
  	cell = pointToCell(room.random(1));
  	if (!heroFOV[cell]
  	&& Actor.findChar( cell ) == null
  	&& passable[cell]
  	&& !solid[cell]
  	&& (!Char.hasProp(ch, Char.Property.LARGE) || openSpace[cell])
  	&& room.canPlaceCharacter(cellToPoint(cell), this)
  	&& cell != exit()) {
  	return cell;
  	}
  	}

  
  Curiously, there is actually a failsafe here, so flooding a normal level with sheep and jumping down will instead cause the game to crash instead of infinitely looping.

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/LastLevel.java

  Lines 169 to 175 in 11c0edc

  	int cell;
  	do {
  	cell = entrance() + PathFinder.NEIGHBOURS8[Random.Int(8)];
  	} while (!passable[cell]
  	|| (Char.hasProp(ch, Char.Property.LARGE) && !openSpace[cell])
  	|| Actor.findChar(cell) != null);
  	return cell;

• Every Boss Level is bugged. These ones are particularly frail because they only encompass a 9 tile area and can infinite loop with just one stone of flock at spawn. Yes, the sewer boss level is slightly less frail, but the same idea still holds.

Level fallCell Methods

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/Level.java

  Lines 1010 to 1017 in 11c0edc

  	public int fallCell( boolean fallIntoPit ) {
  	int result;
  	do {
  	result = randomRespawnCell( null );
  	} while (traps.get(result) != null
  	|| findMob(result) != null);
  	return result;
  	}

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/RegularLevel.java

  Lines 562 to 568 in 4f32d90

  	int result;
  	do {
  	result = pointToCell(room.random());
  	} while (traps.get(result) != null
  	|| findMob(result) != null
  	|| heaps.get(result) != null);
  	return result;

  (Pit room check)

DM 300 Spawning

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/CavesBossLevel.java

Lines 298 to 300 in 4f32d90

	do {
	boss.pos = pointToCell(Random.element(mainArena.getPoints()));
	} while (!openSpace[boss.pos] || map[boss.pos] == Terrain.EMPTY_SP || Actor.findChar(boss.pos) != null);

Ankh Respawn Placement

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/scenes/InterlevelScene.java

Lines 489 to 503 in 4f32d90

	int invPos = Dungeon.hero.pos;
	int tries = 0;
	do {
	Dungeon.hero.pos = level.randomRespawnCell(Dungeon.hero);
	tries++;
	//prevents spawning on traps or plants, prefers farther locations first
	} while (level.traps.get(Dungeon.hero.pos) != null
	|| (level.plants.get(Dungeon.hero.pos) != null && tries < 500)
	|| level.trueDistance(invPos, Dungeon.hero.pos) <= 30 - (tries/10));
	//directly trample grass
	if (level.map[Dungeon.hero.pos] == Terrain.HIGH_GRASS || level.map[Dungeon.hero.pos] == Terrain.FURROWED_GRASS){
	level.map[Dungeon.hero.pos] = Terrain.GRASS;
	}

This one actually has two issues embedded since RandomRespawnCell is bugged.

Short-Sighted Checks

Usually happens because Neighbours8 isn't rigorous enough.

Newborn Elemental Spawning

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/items/quest/CeremonialCandle.java

Lines 103 to 117 in 11c0edc

	ArrayList<Integer> candidates = new ArrayList<>();
	for (int n : PathFinder.NEIGHBOURS8) {
	int cell = ritualPos + n;
	if ((Dungeon.level.passable[cell] || Dungeon.level.avoid[cell]) && Actor.findChar( cell ) == null) {
	candidates.add( cell );
	}
	}
	if (candidates.size() > 0) {
	elemental.pos = Random.element( candidates );
	} else {
	elemental.pos = ritualPos;
	}
	} else {
	elemental.pos = ritualPos;
	}

I see there is a failsafe, but it seems rather exploitable. If that's ok with you, then I don't see a problem either.

Fist Spawning

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/actors/mobs/YogDzewa.java

Lines 420 to 433 in 11c0edc

	if (!Dungeon.isChallenged(Challenges.STRONGER_BOSSES)
	&& (Actor.findChar(targetPos) == null || Actor.findChar(targetPos) instanceof Sheep)){
	fist.pos = targetPos;
	} else if (Actor.findChar(targetPos-1) == null || Actor.findChar(targetPos-1) instanceof Sheep){
	fist.pos = targetPos-1;
	} else if (Actor.findChar(targetPos+1) == null || Actor.findChar(targetPos+1) instanceof Sheep){
	fist.pos = targetPos+1;
	} else if (Actor.findChar(targetPos) == null || Actor.findChar(targetPos) instanceof Sheep){
	fist.pos = targetPos;
	}
	if (Actor.findChar(fist.pos) instanceof Sheep){
	Actor.findChar(fist.pos).die(null);
	}

What if I used bees? Then the fist spawns in the wall.

Yog Spawning

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/levels/HallsBossLevel.java

Lines 232 to 234 in 40b1615

	YogDzewa boss = new YogDzewa();
	boss.pos = exit() + width*3;
	GameScene.add( boss );

The player can spawn into Yog with a stone of blink.

Necromancer minion spawning

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/actors/mobs/Necromancer.java

  Lines 181 to 208 in 1f45564

  	int pushPos = pos;
  	for (int c : PathFinder.NEIGHBOURS8) {
  	if (Actor.findChar(summoningPos + c) == null
  	&& Dungeon.level.passable[summoningPos + c]
  	&& (Dungeon.level.openSpace[summoningPos + c] || !hasProp(Actor.findChar(summoningPos), Property.LARGE))
  	&& Dungeon.level.trueDistance(pos, summoningPos + c) > Dungeon.level.trueDistance(pos, pushPos)) {
  	pushPos = summoningPos + c;
  	}
  	}
  	//push enemy, or wait a turn if there is no valid pushing position
  	if (pushPos != pos) {
  	Char ch = Actor.findChar(summoningPos);
  	Actor.addDelayed( new Pushing( ch, ch.pos, pushPos ), -1 );
  	ch.pos = pushPos;
  	Dungeon.level.occupyCell(ch );
  	} else {
  	Char blocker = Actor.findChar(summoningPos);
  	if (blocker.alignment != alignment){
  	blocker.damage( Random.NormalIntRange(2, 10), this );
  	}
  	spend(TICK);
  	return;
  	}

• shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/actors/mobs/SpectralNecromancer.java

  Lines 109 to 136 in 1f45564

  	&& Dungeon.level.passable[summoningPos + c]
  	&& (Dungeon.level.openSpace[summoningPos + c] || !hasProp(Actor.findChar(summoningPos), Property.LARGE))
  	&& Dungeon.level.trueDistance(pos, summoningPos + c) > Dungeon.level.trueDistance(pos, pushPos)) {
  	pushPos = summoningPos + c;
  	}
  	}
  	//push enemy, or wait a turn if there is no valid pushing position
  	if (pushPos != pos) {
  	Char ch = Actor.findChar(summoningPos);
  	Actor.addDelayed( new Pushing( ch, ch.pos, pushPos ), -1 );
  	ch.pos = pushPos;
  	Dungeon.level.occupyCell(ch );
  	} else {
  	Char blocker = Actor.findChar(summoningPos);
  	if (blocker.alignment != alignment){
  	blocker.damage( Random.NormalIntRange(2, 10), this );
  	}
  	spend(TICK);
  	return;
  	}
  	}
  	summoning = firstSummon = false;

The necromancer/spectral necromancer can push immovable mobs. Technically not as useful as spawning back into the game since you can't use it to arbitrarily move immovable mobs. It can only move immovable things that you spawn in (e.g. wards, dm201), but I doubt this was intended because you can't pull your own wards with ethereal chains.

Returning to a depth

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/Dungeon.java

Lines 430 to 440 in 11c0edc

	for(Mob m : level.mobs){
	if (m.pos == hero.pos){
	//displace mob
	for(int i : PathFinder.NEIGHBOURS8){
	if (Actor.findChar(m.pos+i) == null && level.passable[m.pos + i]){
	m.pos += i;
	break;
	}
	}
	}
	}

Two issues here. One, it doesn't check if the mob is immovable, so you can use this method to move immovable mobs. Second is that this check does nothing if you fill the 3x3 area with mobs (most likely suspect being sheep).

Teleporting via Beacon of Returning

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/items/spells/BeaconOfReturning.java

Lines 122 to 131 in 4f32d90

	moving.pos = returnPos;
	for(int i : PathFinder.NEIGHBOURS8){
	if (Actor.findChar(moving.pos+i) == null
	&& Dungeon.level.passable[moving.pos + i]
	&& (!Char.hasProp(moving, Char.Property.LARGE) || Dungeon.level.openSpace[moving.pos + i])){
	moving.pos += i;
	moving.sprite.point(moving.sprite.worldToCamera(moving.pos));
	break;
	}
	}

Also allows you to move immovable mobs.

Teleporting via Warp Beacon

shattered-pixel-dungeon/core/src/main/java/com/shatteredpixel/shatteredpixeldungeon/actors/hero/abilities/mage/WarpBeacon.java

Lines 134 to 153 in e5d94cc

	Char toPush = Char.hasProp(existing, Char.Property.IMMOVABLE) ? hero : existing;
	ArrayList<Integer> candidates = new ArrayList<>();
	for (int n : PathFinder.NEIGHBOURS8) {
	int cell = tracker.pos + n;
	if (!Dungeon.level.solid[cell] && Actor.findChar( cell ) == null
	&& (!Char.hasProp(toPush, Char.Property.LARGE) || Dungeon.level.openSpace[cell])) {
	candidates.add( cell );
	}
	}
	Random.shuffle(candidates);
	if (!candidates.isEmpty()){
	Actor.addDelayed( new Pushing( toPush, toPush.pos, candidates.get(0) ), -1 );
	toPush.pos = candidates.get(0);
	Dungeon.level.occupyCell(toPush);
	hero.next();
	}
	}

You get to spawn into the mob if there's no space in the 3x3 area. Combined with the beacon of returning, you can use this to move any immovable mob to an arbitrary location on the m

Implications in Practice

Here are some bugs caused by these issues that you may not have seen.

• Use a stone of flock on the stairs in tengu's room and then cast a reclaim trap imbued with a guardian trap. You game will infinitely loop.

• You can softlock yourself in DM300's level by preventing it from spawning via a mass of woolly bombs. (spawned in the items via scroll of debug to save time and applied various buffs to make things more visible, but otherwise no major deviation from base Shattered)
  Video: https://drive.google.com/file/d/142n_duVBLAhCIyba_v2v82klxpTHIy5R/view?usp=sharing
  Save file: dm300-bomb-fire.zip
  ap.
• You can use the ankh to hardlock yourself into a situation where you aren't even allowed to lose by throwing a stone of flock onto the ascending stairs in any boss room.
• You can die by falling on floor 1 (fell from the city above, perhaps?).
• Various exploits for beating bosses using the warp beacon and character stacking.
• The mage with warp beacon can move immovable mobs anywhere on stage.

There are probably more bugs that I forgot about.

Plea for a Proper Fix

Please do not fix this by hardcoding cases for things like bees or sheep. It isn't effective because you can replace it with nearly any other mob, provided you have the right setup. Want a random mob from anywhere? Get a curse of multiplicity and a trusty trap reclaim imbued with distortion. Making a general check for dungeon mobs? Not enough. What if I summoned an army of illusions by collecting enough scrolls via ring of wealth. What if I used ratmorgrify to flood the level? What about the wand of warding? What if I had the patience to flood the level with super mimics via my cursed wand?

I hope this illustrates why you shouldn't just hardcode fixes for this class of issues this time around. It is simply too fragile. We need a strong general fix that applies at the fallCell/randomRespawn level. This is not just for Shattered's good, but all of those who may use it. People are relying on your codebase to be solid. The worst thing that can come out of hardcoding would be teaching new programmers that "bandaging problems" is ok.

Conclusion

Thank you for taking the time to read this monolith of a report. Took me about a month of research to compile and write up these findings. I would have liked to make suggestions on how to handle this issue, but in the spirit of Shattered not taking pull requests, you probably would actively try not to do anything I suggest since it would be very code focused, so I'll stay quiet. Hope you find a good solution to this long-standing issue of spawnblocking in Pixel Dungeon.

[00-Evan]

Thank you for the very detailed report. While I agree that these are code issues with the game, you're seriously exaggerating their impact. Most of what you're talking about here requires extremely specific exploit set ups that essentially require the player to dedicate a run to reproduce bugs that aren't even beneficial to them.

Let me quickly run down your examples:

• Invalid infinite loop: Will only occur if the player purposefully does it, no benefit to an exploiter
• Short-Sighted Space Availability Check: There isn't really a way around unusual behavior here as the game needs to load the level before it can check if there is free space. I prefer this to the alternative of putting the player somewhere other than where they had the beacon. In what way are 'char stacking properties' useful aside from preventing an enemy from attacking before you move away from them? This would seem like an awful lot of work to stack with a single enemy.
• Infinite loops: Only reproducible if the player purposefully fills an entire level with characters, no benefit to an exploiter.
• Boss RandomRespawncell Infinite loops: Just mentioning this one in particular. I still feel that a player is never going to reproduce this accidentally, but I do agree that this is actually reproducible in a normal run.
• Short-Sighted Checks: Fair point about stone of blink into Yog spawn, I agree that one is reasonably reproducible unintentionally, otherwise these stacking failsafes will only happen in very specific circumstances, and I'm fine with their behavior. There's 0 impact but fair enough regarding necromancers and consistency, and the fix is simple.
• Returning to a Depth: I agree that there should be checks for immovable mobs here. Stacking when there is no space is fine for the reasons I mention above.
• You mention "Various exploits for beating bosses using the warp beacon and character stacking." but don't actually say what those are. How does character stacking lead to beating a boss in a way that is more useful than just fighting the boss?

I agree that the code used is not ideal but my goal, ultimately, is to make a videogame, not a codebase that can't be exploited in any way or that is an example of best design practices. If there is a bug that is can only be purposefully reproduced with a lot of dedication, is time-consuming to fix, and provides no incentive to abuse it beyond seeing the bug, then I am not likely to decide to fix it versus working on other things.

With that in mind, I'm afraid I am not going to dedicate the time to reworking the core spawning logic in general cases here. You have highlighted several things that are worth fixing though, and I'll leave this issue open to track that:

• limited space in RandomRespawnCell in boss levels leading to reasonably achievable softlocks with stone of flock
• Necromancers theoretically being able to move immovable characters
• Yog not pushing anything that happens to be on it when it spawns
• Inconsistency and potential to push immovable chars in warp beacon / beacon of returning / generic depth returning

EDIT: upon further consideration, adding a check to prevent crashes when a pit room is full should also be fairly simple, will do that as well. I also don't think that the game will crash if jumping into a full level, as a fallcell of -1 is handled in Dungeon.switchLevel

[gigalh128]

Hey Evan, thanks for the quick reply! Glad you were able to read over these. I understand not going over all of these, but I think that many of the short-sighted availability checks can be solved by killing whatever the player spawns on top of, or preventing the action from happening entirely (e.g. if you cant find space in the 3x3 grid, then don't spawn there).

You mention "Various exploits for beating bosses using the warp beacon and character stacking." but don't actually say what those are. How does character stacking lead to beating a boss in a way that is more useful than just fighting the boss?

https://www.reddit.com/r/PixelDungeon/comments/ws6zj5/clearly_the_intended_way_to_beat_badder_bosses/
I wasn't sure whether or not you would see this on reddit first, so I didn't mention it explicitly. It's particularly good vs the first 3 bosses.

[00-Evan]

Thank you for being more specific about stacking exploits. I hadn't looked over Reddit yet as replying to your original message already sent me way over the time I try to allot to handling message each day. Are you Lighthouse from reddit as well? If so I would appreciate it if you gave me a chance to fix those sorts of bugs before sharing them publicly and thereby amplifying their impact.

Conveniently that one can be fixed with simple checks and cancels given that it all happens within the same level, the case you were referring to previously was about inter-level teleportation.

[gigalh128]

Yes, I am. Sorry, I didn't think it would be an issue to post these types of things because it's an offline game and can't really be used to do anything to anyone but yourself. Guess I'm just used to seeing glitch hunting videos for speedruns.

[gigalh128]

Slightly unrelated, but I'd like to note what "beneficial to the player" means explicitly, as I hadn't realized something very relevant until recently.

You mentioned the following

Most of what you're talking about here requires extremely specific exploit set ups that essentially require the player to dedicate a run to reproduce bugs that aren't even beneficial to them.

I agree that yes, the vast majority of these setups are definitely out of scope of a normal game, but what took me awhile to recognize is that the ability to force crash the game or send it into an infinite loop before a level transition is quite useful for the player. If you can crash the game, you can figure out both items in a crystal chest, use one scroll of identify to figure out all of your items, or re-roll enchantment until you get what you want. Not as related, but something to keep in mind when you think about the definition of "useful for the player". An easy example would be the guardian trap infinite loop. While it may seem stupid to do at first, you can probably see why it is actually a usable exploit with this in mind.

[00-Evan]

That's a fair point about crashes, however I'd say that's only really worth it if the crash is relatively easy to trigger, and as I already stated above I agree that the boss floor infinite loop with sheep is worth adjusting.

[gigalh128]

I couldn't help thinking about it for the past day, but you mentioned the following:

I would appreciate it if you gave me a chance to fix those sorts of bugs before sharing them publicly and thereby amplifying their impact.

I'm curious, but what is the problem with amplifying the impact of exploits in shattered? Although I can't find it, the DM300 exploit patched in 1.3 was posted on social media without any issue brought up about it, and tricks like these can make any% speedruns more interesting to watch, which I'd imagine can improve publicity. Maybe it's just the speedrun enthusiast in me that thinks publicizing glitches in offline games is beneficial, but I'd like to know your reasoning since I can't really understand the issue from my perspective.

[00-Evan]

I should make it clear that I really do just mean that I would appreciate it, you're right that Shattered is single player so I'm certainly not mad if people share bugs. In general I feel that highly beneficial bugs or exploits damage the game experience. If someone knows about the bug, they either use it and trivialize parts of the game, or don't and feel less accomplishment for playing legitimately. The bug will still exist on the current vulnerable versions so if people want to speedrun that this shouldn't stop them.

Just as a more extreme example, I am very happy that I was able to fix the 'multiple descend' bug before it became general knowledge (resize the game window X times to descend X additional depths), as the bug would make it extremely easy anyone to immediately get a win.

[spixi]

@gigalh128 I also noted an infinite loop for the blob / shard drop of exotic enemy variants which could be reproduced with spider webs (that issue #556 was fixed in 0.9.1b). I don't think if there is a real solution for the problem. Sure, you can despawn some sprites like sheep, but as you said, also other sprites like ratmogrified enemies, mirror images etc. can fill up space and prevent things from spawning. I think, there should be a kind of failsafe, whenever a mob or an item cannot be spawned. That would be better than an endless loop. Maybe you could say: Try to despawn sprites in a certain order (no bosses or NPCs) and if even that is not possible, skip the spawn or crash with a message if that would affect a story-related mob, item, key (including the key leading to the first prison boss room) or the player themselves.