Directions Evolved


Jonathon Duerig recently posted the following comment on the Some New Direction article.

I really like this idea and was inspired to put this in my own project. However, I’m stumped on how to put in relations between into it. I want to be flexible enough for algorithms based on the directions to be able to use four-way, eight-way, up and down, etc. kinds of directions without modification.

I also want to work with directions in terms of a relationships between them. I want to be able to find the next direction clockwise of a given direction, for instance. Or choose a random direction perpendicular to a given direction. Or find the direction opposite of a given direction.

Having a flexible interface to setup these relationships at startup is proving difficult. Ideas?

-D

I rambled off an initial response without actually thinking about the problem and why he needed this functionality. I started thinking about his request and realised that it would be quite useful. Hence this blog post.

I am going to deal with the relationships between directions first. Lets say we would like to find the next clockwise direction. The test for this functionality looks as follows.

        [TestMethod]

        public void TestNextDirection()

        {

            Assert.AreEqual(Direction.Northeast, Direction.North.Next);

            Assert.AreEqual(Direction.East, Direction.Northeast.Next);

            Assert.AreEqual(Direction.Southeast, Direction.East.Next);

            Assert.AreEqual(Direction.South, Direction.Southeast.Next);

            Assert.AreEqual(Direction.Southwest, Direction.South.Next);

            Assert.AreEqual(Direction.West, Direction.Southwest.Next);

            Assert.AreEqual(Direction.Northwest, Direction.West.Next);

            Assert.AreEqual(Direction.North, Direction.Northwest.Next);

        }

In the above test we make use of the new “Next” property on the Direction class. The idea is that the “Next” property returns the next clockwise direction based on our current direction.

The code that makes the above test compile is as follows.

        /// <summary>

        /// The next clockwise direction of the current direction

        /// </summary>

        public Direction Next

        {

            get

            {

                switch (Name)

                {

                    case “North”:

                        return Direction.Northeast;

                    case “Northeast”:

                        return Direction.East;

                    case “East”:

                        return Direction.Southeast;

                    case “Southeast”:

                        return Direction.South;

                    case “South”:

                        return Direction.Southwest;

                    case “Southwest”:

                        return Direction.West;

                    case “West”:

                        return Direction.Northwest;

                    case “Northwest”:

                        return Direction.North;

                    default:

                        throw new InvalidOperationException();

                }

            }

        }

In the above listing we hardcode the next clockwise direction for the current direction using a simple case statement. I compile the code and rerun the test. It passes with no issues.

I won’t cover the implementation for the other relationships between directions as they are almost identical to the one above. The additional properties I added are “Previous”, “NextPerpendicular” and “PreviousPerpendicular”. The “Previous” property returns the next anti-clockwise direction. The “NextPerpendicular” and “PreviousPerpendicular” properties return the next clockwise and anti-clockwise perpendicular directions respectively.

The class diagram for the direction class is now as follows.

Direction class diagram

The next part of the functionality he required was to be able to limit the number of directions available. In my initial response I recommended a helper class such as the DirectionPicker class I used in my DungeonGeneration article series.

In order to support working with different combinations of directions we need to modify the DirectionPicker class to use a list of available directions for all its operations.

The current implementation picks a random direction (previously only the main compass directions north, east, south and west) and adds it to a list of directions picked. By specifying a list of available directions we can implement the same functionality by removing the direction picked from the provided available directions.

The random direction is now selected by choosing a random index within the list of available directions. This allows us to select random directions in any combination as specified by the available directions.

The code affected by these changes can be seen below (the original code has been commented out)

       public bool HasDirectionToPick

        {

            get

            {

                return directionsAvailable.Count > 0;

                //return directionsPicked.Count < 4;

            }

        }

 

        private bool MustChangeDirection

        {

            get

            {

                // changeDirectionModifier of 100 will always change direction

                // value of 0 will never change direction

                return ((directionWasPicked) || (changeDirectionModifier > RogueLib.Common.Random.Instance.Next(0, 99)));

                //return ((directionsPicked.Count > 0) || (changeDirectionModifier > RogueLib.Common.Random.Instance.Next(0, 99)));

            }

        }

 

        private Direction PickDifferentRandomDirection()

        {

            Direction directionPicked;

            do

            {

                directionPicked = directionsAvailable[RogueLib.Common.Random.Instance.Next(directionsAvailable.Count – 1)];

                //directionPicked = directionsAvailable[RogueLib.Common.Random.Instance.Next(3)];

            } while ((directionPicked == previousDirection) && (directionsAvailable.Count > 1));

            //} while ((directionPicked == previousDirection) && (directionsPicked.Count < 3));

 

            return directionPicked;

        }

 

        public Direction PickRandomDirection()

        {

            if (!HasDirectionToPick) throw new InvalidOperationException(“No directions available”);

 

            Direction directionPicked;

 

            do

            {

                directionPicked = MustChangeDirection ? PickDifferentRandomDirection() : previousDirection;

            } while (!directionsAvailable.Contains(directionPicked));

            //} while (directionsPicked.Contains(directionPicked));

 

            directionsAvailable.Remove(directionPicked);

            //directionsPicked.Add(directionPicked);

 

            directionWasPicked = true;

            return directionPicked;

        }

I created three constructors to allow me to easily configure the available directions for the DirectionPicker. The default constructor makes use of the main compass directions (north, east, south, west) as was the default behaviour before we made the above changes.

The second constructor takes a DirectionsAvailableType enum as input parameter and sets up the available directions based on the provided DirectionsAvailableType. The two available types are AllCompassDirections and MainCompassDirections.

The third constructor takes a params array of Directions as input parameter whereby the user can specify a custom list of available directions. I would use this constructor to satisfy Jonathon’s requirement of selecting a random perpendicular direction to a given direction for example.

        [TestMethod]

        public void TestSelectionOfRandomPerpendicularDirection()

        {

            Direction currentDirection = Direction.North;

            DirectionPicker directionPicker = new DirectionPicker(Direction.North, 100, currentDirection.PreviousPerpendicular, currentDirection.NextPerpendicular);

            List<Direction> directionsPicked = new List<Direction>();

            directionsPicked.Add(directionPicker.PickRandomDirection());

            directionsPicked.Add(directionPicker.PickRandomDirection());

 

            Assert.IsTrue(directionsPicked.Contains(currentDirection.PreviousPerpendicular));

            Assert.IsTrue(directionsPicked.Contains(currentDirection.NextPerpendicular));

            Assert.IsFalse(directionPicker.HasDirectionToPick);

        }

In the above test we instantiate our direction picker with the previous (West) and next (East) perpendicular directions from our current direction (North). We then instantiate a new list that will contain the directions picked and then proceed to pick two random directions. The test then asserts that both the perpendicular directions were indeed selected and that there are no more directions available for selection.

The above improvements to the Direction and DirectionPicker classes have added great flexibility to our Direction handling code. Any suggestions or comments would, as always, be appreciated.

Advertisements

One thought on “Directions Evolved

  1. I have come back to my own little project after a while and I thought I’d share with you how I ended up approaching the problem. The first big difference is that my approach is table-based rather than control-flow based. The second difference is that I ended up going with the notion of a ‘compass’ which sets up directions according to a set formula rather than having a standard set that you can pick subsets of.

    In terms of tables, I have a series of private arrays which take an index and return some specified value. This could be the name, the unit point for the direction (dx, dy), the reverse of the direction, etc. The direction itself contains only the index and the member functions which return the various characteristics just lookup in the tables. This also makes directions value objects where identity doesn’t matter any more. For comparison, you can just compare index values.

    Initialization is a slightly complex affair. First, you call init_direction() for each direction you care about giving the name and the unit point. init_direction() returns the actual direction which you can store somewhere convenient. Then you call init_reverse(), init_rotation(), and init_rotation_90() on pairs of directions to set up the relationships. Since this is so complicated, I encapsulated the common case into a compass.

    The notion of compass is that the user selects a single kind of compass for the entire program and calls the init() function on that compass when setting up. The init() function sets up all of the directions and their relations depending on what the compass is. A four-point compass would set up only the directions north, south, east, and west. An eight-point-compass would set up only the directions north, south, east, west, northeast, northwest, southeast, southwest. But the user could create their own compass which had all of the above directions but also had ‘up’ and ‘down’ or ‘center’ or whatever. The identifiers north, south, etc. are also defined inside the compass.

    -D

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s