Friday 8 March 2013

Boolean logic, or the art of making the simple complex

I've been slowly rewriting big chunks of code, i've basically decided to rewrite almost everything apart from the battle system, but it's days may also be numbered.

Things are looking promising because I finally understand why some parts of the code is so complicated where it doesn't seem to need it - it's trying to monitor changes of state every time they happen and then propagate thing to the client. This just isn't necessary, all it needs to do is keep track of 'what i think the client has' (which it does already), and then perform a search of 'what the client should have' at the end of every turn and propagate that to the client. No need to have some convoluted cascade of 'you can now see this, lets set it right now and incidentally use that to track other state at the same time'. Because it's already doing the former anyway to implement the latter ... which also means extra update messages.

But that is not the topic of this post.

There is also quite a bit of convoluted logic which is hard to decipher. For example when an entity tries to follow another one. I will break it into two parts, 'can you do this', and 'do this'.

First, the 'can' test:

    if (lt.isSleeping) {
        return "You can't do that while you're sleeping";
    }
    DuskObject objStore = lt.getLocalObject(args);
    if (objStore == null) {
        return "You don't see that here.";
    }
    if (objStore.isLivingThing()) {
        LivingThing thnStore = (LivingThing) objStore;
        if (lt.getMaster() != null && thnStore != lt.getMaster()) {
            if (lt.isPet()) {
                return "You can only follow your owner.";
            }
            return "You're already following someone. Leave them first.";
        }
        if (Math.abs(lt.x - thnStore.x) + Math.abs(lt.y - thnStore.y) > 1) {
            return "They're too far away.";
        }
        if (thnStore == lt) {
            return "You can't follow yourself.";
        }
        if (!thnStore.isPlayer() && !lt.isMob()) {
            return "You can only follow players.";
        }
        if (thnStore.noFollow || (thnStore.isPet() && thnStore.getMaster().noFollow)) {
            return "They won't let you follow them.";
        }

Here 'lt' is the thing that wants to follow, and 'objStore' and 'thnStore' are the thing it wants to lead it.

The tests in order ...

Sleeping?
Obvious.
Visible in surrounding area?
Obvious.
LivingThing?
Only LivingThings can move and fight.
Already following something?
Can only follow one leader, pets can only follow their owner.
They're on an adjacent location?
Proximity test.
Insanity test.
Obvious.
Player/Pet can only follow Player. But mobs can follow anything.
This was the hardest bit to understand ... blah. I got it wrong a few times and much refactoring ensued.
Honour no-follow setting
Pets are treated as proxies for their masters.

The problem is not so much the amount of code - although this type of logic is littered throughout the code-base - it's understanding the finer points. Just looking at that it's pretty hard to tell who can be leaders - e.g. can you follow a pet.

It does a lot of tests so it can't really be simplified much but maybe it can be made more obvious. I tried implementing it over the 4 Active/Player/Pet/Mobile classes by using the class structure to most of the need for the 'what am i' checks.

First, the code in Active:

public void follow(Active master) {
  if (sleeping) {
        chatMessage("You can't do that while you're sleeping");
        return;
    }
    if (distanceL1(master) > 1) {
        chatMessage("They're too far away.");
        return;
    }
    if (group != null) {
        chatMessage("You're already following someone. Leave them first.");
        return;
    }
    if (this.ID == master.ID) {
        chatMessage("You can't follow yourself.");
        return;
    }
    if (!isCanLead()) {
        chatMessage("They won't let you follow them.");
        return;
    }

This does the generic tests applicable to all classes. I've done some obvious things like add a distance measure function - rather than cut and paste the code everywhere. The isCanLead() is overriden in the Pet to proxy it's master's setting rather than having to have a class test inline.

Player only needs to add an additional test to ensure they're following a Player either directly of via a Pet.

public void follow(Active master) {
    if (master.getType() != TYPE_PLAYER
        || master.getType() != TYPE_PET) {
        chatMessage("You can only follow players.");
        return;
    }
    super.follow(master);
}

Pets can only follow their owner so don't need the "is it a player" test.

public void follow(Active master) {
    if (this.master.ID != master.ID) {
        chatMessage("You can only follow your owner.");
        return;
    }
    super.follow(master);
}

And Mobile just uses the Active method.

I think that covers all the cases and defines the same behaviour? The local-visibility and 'is it a living thing' tests are performed before it gets to this point for obvious reasons.

To me it is simpler, and the class types enforce behaviour at the language level and so are less error prone.

The downside of this is that the logic is now scattered over 4 separate files. Tooling helps to track what's going on, but it still requires some effort. Another problem is that adding such specificity in the class structure means changes are more difficult and perhaps costlier. For some reason I can't recall I nearly added this extra level in the class structure at this point before, I think it might be useful elsewhere (battle code).

And now the 'do' bit:

        if (lt.isPet()) {
            thnStore.setFollowing(lt);
            lt.setMaster(thnStore);
            thnStore.updateStats();
            lt.updateStats();
            return "You are now following " + lt.getMaster().name + ".";
        }
        LivingThing thnStore2 = thnStore;
        while (thnStore2 != null) {
            if (lt == thnStore2) {
                return "You're already in that group.";
            }
            thnStore2 = thnStore2.getMaster();
        }
        thnStore.chatMessage("You are now being followed by " + lt.name + ".");
        while (thnStore.getFollowing() != null) {
            thnStore = thnStore.getFollowing();
            if (thnStore.isPlayer()) {
                thnStore.chatMessage("You are now being followed by " + lt.name + ".");
            }
        }
        thnStore.setFollowing(lt);
        lt.setMaster(thnStore);
        thnStore.updateStats();
        lt.updateStats();
        return "You are now following " + lt.getMaster().name + ".";
    }
    return "That's not something you can follow.";

The pet part is fairly obvious (and again you see the immediate update calls, whereas a 'has changed' indicator would suffice). Although if the player is already following someone, it seems to just overwrite the link pointers - corrupt list?

But the rest is kind of not too obvious - and I suspect buggy anyway.

First some background to explain the loops. The entities use two pointers 'following', and 'master' to create a double-linked list of the 'following' group to which the entity belongs. This is for movement but mainly for battle (and knowing this will help me simplify the battle code too). Although there is a direct ordering relationship, it isn't really used apart from notification - when you follow you're placed at the end of the group.

So the first loop just determines if you're already in the pack. It only checks in one direction though which I think is a bug.

The second loop notifies everyone else in the pack that you've just joined. Again it only checks in one direction, which think is also a bug.

And finally the Active is linked into the end of the group, and stats updated.

I suspect this doesn't work very well in practice as you need to be next to someone to follow them, but if you follow the leader you are actually set to follow someone at the end the a conga line. I think this will immediately break when you move, since you need to be adjacent for movement.

What's worse this confusing ('thnStore'??) and error prone double-linked-list code is littered throughout the code - this snippet came from the command executor, but it is repeated throughout LivingThing, DuskEngine, and Script in several places.

ADT to the rescue!

The first big thing is to just wrap the pack in an ADT. A list is pretty much enough but since it probably needs some policy enforcement I wrapped it in a new Group object (actually I might call it Pack since Group is a bit too generic).

The code then becomes something like below, although i'm still trying to work out what's going on with the pet mechanism - I probably need a separate relationship for that. Actually now I think about it, perhaps a completely separate mechanism should be used for Pets to follow Players.

    if (master.group == null) {
        master.group = new Group();
        master.group.addFollower(master);
    }

    for (Active a: master.group.members()) {
       a.chatMessage("You are now being followed by " + name + ".");
    }

    group = master.group;
    group.addFollower(this);

    chatMessage("You are now following " + master.name + ".");

Which I think we can all agree is a marked improvement.

Whilst writing this I re-designed this stuff several times, mostly trying to understand that one troublesome if statement in the can follow block. I'm sure it isn't finished either - one I delve into the battle code I might find surprises.

Just start from scratch?

I guess I wasn't quite at the top of my game when I looked at this (it's been a long week, apart from 30+ hours on dusk i've done 30+ hours for work) - but it took far too long just to work out what was happening here. Trying to understand someone else's code - even in such a simple and harder-to-abuse language like Java - is pretty much a headfuck. It rapidly gets to the point where starting from scratch becomes an attractive proposition.

The server code less the scripting engine is only about 6KLOC (counting semicolons). If I fully knew what I wanted to do and didn't need to muck around making decisions or writing big blog posts I could easily polish that off in a week or two - and still have long weekends.

Although and i'm pretty sure it can be done in significantly less actual code anyway (but the deeper object hierarchy will add some overhead in locs).

Poking continues ...

No comments: