ID:2381423
 
One of my biggest irritations with MoveLib was that it was a cumbersome, heavy piece of shit library that solved a lot of problems in really bad ways.

I learned a lot maintaining and developing it. For starters, how I was handling partial pixel preservation was not good. The main source of bugs was the fact that I was allowing nested movement calls to muck with the process, and avoiding encapsulating information into datums to avoid overhead. It really made the whole problem way worse than it needed to be.

I've been attempting to rectify some of the problems with MoveLib by planning around an entirely new internal structure while maintaining an extremely similar API for developers to use.

I wanted some input on some of these new ideas from other developers, and how to best implement some of these things in such a way that my code isn't getting in the way of how you like to write your code (BTW, it's wrong. Your code is always wrong. You don't matter. Give up. =P... Kidding of course.).

Below I'll be bantering about design considerations I'm messing with right now, and would appreciate some input if y'all got the time or inclination.
One of the things that really irked the living shit out of me was canceling a movement.

Let's say we have a tile that once you step inside of it, it stops your current movement and redirects you in another direction, or even teleports you elsewhere on the map. This is kind of a weird thing to do, but in theory it's a valid concept.

The code:

turf/redirect
Entered(atom/movable/o)
..()
step(o,dir,32)


Here's what this code winds up doing:

Move()
    Exit()
    Enter()
    Exited()
    Entered()
    Move()
        Exit()
        Enter()
        Exited()
        Entered()
    //Move #1 continues here, wiping out the
    //last movement and teleporting them back
    //along their original path of motion


The original movement:


What we want to happen:
First movement in blue. Canceled portion of the first movement in red. Second movement in purple.


What actually happens:
First movement in blue. Second movement in purple. After completing second movement, position of mover acts as though they were continuing from the point where the second movement began, ending at the desired position of the first movement instead of the second.


This is actually only a major problem when moving over large distances. One means of solving this problem, at least in part is to spawn(0) before attempting to move the player again. Unfortunately, this results in the player potentially overshooting their desired position a good bit.

With spawn(0):

turf/redirect
Entered(atom/movable/o)
..()
spawn(0)
step(o,dir,32)




With this example, we'd have to do a bunch of fuckery to get the player in the right position, but in my opinion, the player never should have reached the desired position for the first move in the first place, so backing that out is just going to straight up be a pain in the ass and require a lot of work that really ought not need to be done in the first place.

Fixing it:
turf/redirect
Exit(atom/movable/o,atom/toloc)
. = ..()&&(toloc?.z!=z||get_dir(src,toloc)==dir)

Entered(atom/movable/o)
..()
spawn(0)
step(o,dir,32)


This results in the desired result:




But even so, this is a solution to only a single one of the situations you may want to account for each different situation requires a totally different approach, or some kind of fucky storage system in the global space, in a mob variable, or on the turf type.

I came up with a better solution today, and wanted to run it by some people to see what they think about the potential for issues with other peoples' code:

turf
Enter(atom/movable/o,atom/fromloc)
. = !o.moving.canceled && ..()

Exit(atom/movable/o,atom/toloc)
. = !o.moving.canceled && ..()

atom
movable
var/tmp
move_event/moving

Move(atom/NewLoc,Dir=0,Step_x=0,Step_y=0)
moving = new/move_event(src,NewLoc,Dir,Step_x,Step_y)
. = ..()
moving = moving.last

Del()
moving = null
..()

move_event
var
atom/movable/mover
atom/old_a
old_d
old_x
old_y
atom/new_a
new_d
new_x
new_y

move_event/last
canceled = 0
id = 1

New(atom/movable/m,atom/a,d,x,y)
mover = m
if((last = m.moving))
id = last.id+1
last.canceled = 1
old_a = m.loc
old_d = m.dir
old_x = m.step_x
old_y = m.step_y
new_a = a
new_d = d
new_x = x
new_y = y


The above code results in our desired solution:



The major issue with this is that any Enter()/Exit() procs that override the default action for the library and return 1 without checking themselves whether the movement is still valid will actually prevent the cancellation of nested movements and put us right back in the same mess. I don't think this is really an issue, as ideally you should be at least consulting the default action prior to changing the outcome in almost every case.

Anybody see any major headaches to using something like this?
Another major annoyance with the old rendition of MoveLib was that if you wanted to use macros to get the global pixel position of an object, it would actually have to reference the ref argument 4 times.

This is a problem because it's possible to pass an argument into the macro and get inconsistent results, unlike a proc.

Using a macro virtually halves the CPU usage of this calculation over a proc. The main issue, however, is that to make the macro reference work the same way a proc would, would require storing the reference in a global variable, which would create garbage collection issues if not cleared, and there was no clean way to clear that information in every case you might want to use the macro.

I have managed to come up with a safer approach to doing this:

var/atom/__tmp_ref
#define global_step_x(ref) ((__tmp_ref=(ref)) ? (__tmp_ref.x-1)*TILE_WIDTH + __tmp_ref.step_x + __tmp_ref.bound_x + (__tmp_ref=null) : 0)


Thanks to operator chaining, I am actually able to use the assignment operator as a part of the macro to unset the __tmp_ref after I'm done using it. This may look more confusing than the original library's rendition of the operation, but the result is actually identical in use while being significantly faster. It also suffers no design caveats further down the road.
Yet another issue that I had with MoveLib was in temporarily changing the rules for movement of an object.

BYOND's pixel movement system depends on the mob's step_size for an awful lot of things. One of the bigger issues is that Move() can either be a jump or a slide. A jump only tests the two endpoints of the movement, so you will effectively jump over anything in between the two objects.

If you wanted to move an object in MoveLib a good distance taking obstacles into account, you needed to change the step_size to do it. MoveLib assumed that if you were using Move(), you actually wanted a slide instead of a jump, and attempted to restore the old step size after the movement was finished.

Unfortunately, permanent changes to step_size after Entered()/Exited()/Bump() could wind up being wiped out by this, making step(), walk(), etc. potentially unsafe to use.

I don't like blocking off the default behavior, I'd rather roll it in under my own system.

Once again, I've implemented move_speed, which is a variable that by default is null. If not set, it defaults to the value of step_size. This allows me to actually safely mess around with step_size as well as restore it. The only catch here is that step_size is still unsafe to change inside of a movement. Instead, move_speed should be the value that you change to permanently change how far the player can move per step by default. The additional benefit to having this variable is in preserving partial pixel movements, as step_size is limited to integer values.

Unfortunately, there's really no good way around this, and step()/walk() should be considered unsafe to use without dist arguments only during a movement. The best way to work around this is to override all of the built-in stepping and walking functions, and write some custom logic that will allow the built in functions to default to using ref.move_speed instead of ref.step_size

proc
__step(atom/Ref,Dir,Speed=0)
return step(Ref,Dir,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__step_away(atom/Ref,Trg,Max=5,Speed=0)
return step_away(Ref,Trg,Max,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__step_rand(atom/Ref,Speed=0)
return step_rand(Ref,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__step_to(atom/Ref,Trg,Min=0,Speed=0)
return step_to(Ref,Trg,Min,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__step_towards(atom/Ref,Trg,Speed=0)
return step_towards(Ref,Trg,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__walk(atom/Ref,Dir,Lag=0,Speed=0)
walk(Ref,Dir,Lag,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__walk_away(atom/Ref,Trg,Max=5,Lag=0,Speed=0)
walk_away(Ref,Trg,Max,Lag,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__walk_rand(atom/Ref,Lag=0,Speed=0)
walk_rand(Ref,Lag,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__walk_to(atom/Ref,Trg,Min=0,Lag=0,Speed=0)
walk_to(Ref,Trg,Min,Lag,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

__walk_towards(atom/Ref,Trg,Lag=0,Speed=0)
walk_towards(Ref,Trg,Lag,max(1,Speed||(istype(Ref,/atom/movable)&&Ref:move_speed)))

#define step(ref...) __step(##ref)
#define step_away(ref...) __step_away(##ref)
#define step_rand(ref...) __step_rand(##ref)
#define step_to(ref...) __step_to(##ref)
#define step_towards(ref...) __step_towards(##ref)
#define walk(ref...) __walk(##ref)
#define walk_away(ref...) __walk_away(##ref)
#define walk_rand(ref...) __walk_rand(##ref)
#define walk_to(ref...) __walk_to(##ref)
#define walk_towards(ref...) __walk_towards(##ref)


This induces some overhead for sure, but it is a better solution than ensuring that developers always use my wrapper functions or janky movement workarounds.
I wanted to take some time to describe edge and corner sliding. These are fundamental concepts to making pixel movement games feel intuitive.

Let's focus on edge sliding first.

What is edge sliding? Edge sliding is when you are moving diagonally, and encounter an obstacle. BYOND will by default stop all motion across both axes, because your movement is obstructed. However, most players expect that diagonal motion is actually a compound motion, and will continue to attempt to move along the unblocked axis. This is not an unreasonable expectation. You should not have to fight your playspace just to do something as simple as moving.

Here's a diagram that shows this in action. The blue line is the original movement. Purple lines are what one would logically expect movement would do in response to failure of the original movement:



And here's with an edge sliding solution in play:



The naive solution would be to simply try to move the remaining distance of a failed diagonal movement along the unblocked axis of motion. Unfortunately, that's problematic, as is demonstrated in the following situation:



In this situation, the player is sliding along a wall with a gap just large enough to fit in. Without a better algorithm than just continuing the movement in the event of a single-axis failure, the player will pass right over that opening rather than what they may expect to happen: Sliding into that gap.

Instead, what we would expect to happen:



This example shows that there are four potential collision cases for obstructed diagonal movement:



The above image shows these collision cases for the given motion (southeast). You'll notice that I've shadowed a full tile area in a lighter color than the edges abutting the player's tile. That's to illustrate the fact that only a portion of that area is necessary to test for collision during the southeast motion. Let's look at some combinations to demonstrate the expectations:



In the above image, there are 4 cases, each with two permutations. Case 1 and 2 concern blockages along the x and y axis only. Notice how the presence of the corner doesn't change the outcome? Case 3 concerns both the x and y axis being blocked. Notice how the presence of the corner again, doesn't change the outcome?

In case 4, only the corner is blocked. This is the one case where more information is necessary in order to decide what to do. Deciding which side to move toward in the case of only an obstructed corner is called a bias. In most cases, a horizontal bias is preferable to a verterical bias, but that is not always true. the particulars of your game's playspace will determine the preferred bias. In the case of a sidescroller, horizontal bias will almost always be preferred. In the case of a top-down or 3/4ths game, however, bias may be preferred by keeping track of orientation of the last single axis motion. To make this more simplistic, you may want to keep track of whether the player was moving north/south or east/west prior to beginning to move diagonally. This can be used to decide which direction a blocked corner on a diagonal movement will prefer to slide along.

All of this information begins to form a process:

1) If moving diagonally, and we encounter an obstacle, we need to check the 3 regions abutting the direction the player is moving in and determine which are blocked.

2) To determine how far we can move, we need to check the axis that we slide along. We can call this region the "rail". We need to find the edge of the furthest obstacle in the rail and move the minimum of the distance to that edge, and the axial distance that was stopped from the diagonal movement.

3) If we still have remaining axial motion stored, attempt to move in the original diagonal direction for the remaining distance again, repeating step #1 if an obstacle is encountered.
The second bit about sliding we need to wrap our heads around is corner sliding. Like edge sliding, corner sliding is only necessary for some blocked movements. Instead of only happening when moving diagonally, it only happens when moving along a single axis, rather than while moving along both.

First we need to outline a few concepts. One of the concepts for corner sliding is called a "lip". A lip is a section of a bounding box that when obstructed, will apply pressure to move the bounding box to a point where it is no longer obstructed.

Bounding box lips can be of arbitrary size, and can even overlap one another. Let's take a look at a diagram of a 16x16 bounding box with 4px lips on all sides:



The green area represent the lip regions on the bounding box.

Let's also show a diagram of what we expect from a lip collision:



In the above diagram, only one lip is encountered in the collision, thus we should move the object northward by the size of the obstruction relative to the size of the lip, and then perform the original expected motion.

This allows players to more easily get into gaps in your playspace without having to precisely line up the edges of their bounding box. Using both edge and corner sliding makes moving through a complicated playspace effortless and smooth. These two concepts are completely necessary to any game that uses pixel collision.

It should be noted, however, that not all games will require corner sliding along every axis. For instance, sidescrolling games may only require edge sliding along the following corners:



The reason for this would be allowing stair climbing:



As well as preventing edge hovering:




Lastly, we need to go over a couple of collision cases and the expected outcome:



The above images starts to give us a general overview of how to do the above:

1) if moving, but not diagonally, and we encounter an obstacle, we need to get all objects abutting the forward edge of the bounding box.

2) Loop over these objects, first checking whether the objects are obstructions, if so, store the minimum and the maximum x for the north or south edge, or maximum and minimum y for the east or west edge.

3) Compare the minimum and maximum x and y values to the positions of the lips. Provided there are obstructions within the lip area, but not above the lip area, set a pressure flag for the required direction. If both pressure flags are on, do nothing.

4) If only one flag is on: Get a list of all obstacles the player is currently overlapping (list A). Get all potential obstacles the player would be overlapping if they stepped to avoid the corner we're colliding with (list B). Finally, get a list of all obstacles the player would be overlapping after stepping 1 pixel past the corner (list C).



5) Loop over A minus B. Call Uncross(). If any fail, eject early.

6) Loop over B minus A. Call Cross(). If any fail, eject early.

7) Loop over B minus C. Call Uncross(). If any fail, eject early.

8) Loop over C minus B. Call Cross(). If any fail, eject early.

9) Assuming none of the above failed, move the player by the minimum of the obstructed lip distance or the original step size.

10) Finally, perform the original movement.