Announcement: Be excellent to each other.

Caravel Forum : DROD Boards : Bugs : Stalwarts and walls (Build 82)
New Topic New Poll Post Reply
Poster Message
Level: Master Delver
Rank Points: 162
Registered: 04-08-2007
IP: Logged

File: Stalwart bug.hold (967 bytes)
Downloaded 32 times.
License: Public Domain
icon Stalwarts and walls (+2)  
Sometimes, walls can affect stalwart movement when walls are not in the stalwarts' way. Look at the attached hold.

[Last edited by Mazer at 05-10-2008 04:36 PM]
05-10-2008 at 04:35 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Level: Smitemaster
Rank Points: 3093
Registered: 06-11-2007
IP: Logged
icon Re: Stalwarts and walls (+5)  
Yeah, that's been around for a while. And it boils down to something we were kinda always iffy about, but nevertheless use: our priority_queue used there does not use strict weak ordering (don't worry if you don't know what that means). (EDIT: Actually, I'm blaming the wrong thing here - it's more to do with the fact that priority_queues don't internally have a way of deciding ties between equal priorities... and since we don't give it one, we can't expect anything good from it.)

Essentially, a Stalwart works out what path to take as follows:
1) Starting at the square it stands on, it compares each square around it in turn with a particular priority: N, E, S, W, NE, SE, SW, NW.
2) From each of *those* squares, it checks the squares around them in the same priority. It never revisits squares that have already been defined though, and always takes the lowest scores (the amount of steps it took to reach that square).
3) The search ends when a monster is found or all reachable tiles are exhausted. Squares are checked in turn as the expansion happens, with priority given in the following way:
* Tiles that are closest to the Stalwart along the path have highest priority: so we work out all tiles that are 2 steps away before touching any that are 3 steps away.
* Tiles that we got via a certain direction from the previous tile have higher priority than other directions: again, we go over all tiles we went N to get to before checking those that we went E to get to, and so forth.
* If any ties exist after those two (and many *many* ties will), then we just rely on the ordering system to deal with it. However, instead of always picking the last or first tile to be found, we're at the mercy of the algorithm, and so there is *no* such predictable ordering system to break this tie. It relies completely on things like how many ties there are to break and how big the queue is that we're trying to sort. In essence: it's psuedo-random.

Here's the map of the room for the first four squares + goal around the Stalwart for both rooms, using - and | for cardinal and \/ for diagonal directions, and with the "chosen path" bolded:
Room 1:

Room 2:

Of course, it'll only follow that path for the *first* step, and then recalculate it again next turn, so that won't be the complete path it follows. But there's no way we can predict this.


And here's the kicker. This is the same algorithm that Slayer Wisps use. And Halph uses to find orbs. As crazy as this system is, it is *deeply* entrenched into the game. It will affect *every* room with either of these three elements that you can think of - it's not even like the Seep/Waterskipper pathmapping issue I brought up, which only comes into play semi-rarely.

This style of pathmapping is also the reason why Wisps and Stalwarts don't like walking directly alongside walls (and instead prefer staying one square away while they're following it)... and since that aspect has already been used as puzzle fodder....

That's all I can really say, I'm afraid. I've made an example of this sort of behaviour before, but this is a particularly simple and glaring example you've come up with, so thank you for that.

[Last edited by TFMurphy at 05-11-2008 04:42 PM]
05-11-2008 at 03:22 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
Level: Roachling
Rank Points: 10
Registered: 08-25-2009
IP: Logged
icon Re: Stalwarts and walls (0)  
Shouldn't this be easy enough to fix by modifying the priority_queue's comparator functional?

As a simplest example (but perhaps this would work just fine in practice), if two tiles have tied priorities under the current metric, return the one with least x coordinate as the "lesser" tile, and if both tiles have the same x coordinate, look at y.
08-25-2009 at 09:53 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
New Topic New Poll Post Reply
Caravel Forum : DROD Boards : Bugs : Stalwarts and walls (Build 82)
Surf To:

Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us |

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.