Paths are hard

I almost never estimate correctly; it’s freak’n difficult. That being said, for a project like mine it doesn’t really matter because all progress is done linearly by just me. The only stakeholder is me and only I am suffering from blown out time frames.

I consider Failed State (as I’m currently making it) a first draft app. I’ll hurriedly make it to some kind of limited scope, ship it, then look back on it and see how it can be edited, e.g. better code integrity, better modularisation etc. For now, I don’t care too much because:

  1. I’m just learning Unity so naturally I’m unfamiliar with best practise still, and
  2. I just need to ship something. I’m not after creating some kind of architectural masterpiece. This is not medical software so bugs aren’t going to be detrimental.

This past week my expectations of progress have been dashed by path drawing. It turns out it’s not that simple. Well, conceptually it’s simple but trying to code and and seeing the result being rendered using those naive assumptions, it becomes quickly apparent that more thought is required.

Work flow (simple version)

  • The user clicks on (touches) a unit and drags a path out from that unit.
  • The pathfinding library calculates a new path in case some impassible objects have to be avoided. If there are no obstacles, the user drawn path and the path-lib path will be the same.
  • A rendered line follows that new path
  • As the path is being ‘drawn’ by the user/player, the unit begins to follow that path even if the path has not been completed yet.
  • As the path is followed by the unit, the rendered line is cropped as it is ‘consumed’ by the unit that is following it

Unfortunately it’s not that simple.

Work flow (more complex version)

  • The user clicks/touches a unit. This only selects the unit, i.e. making it “ready to be given a path to follow”.
  • A drag start event creates the first major waypoint; we’ll call it the 0th major waypoint. Major waypoints are the points that make up the user drawn line and ordinary waypoints are what the pathfinding library generates.
  • With the number of major waypoints greater than zero and the targetMajorWaypoint still at zero, this special case means that the pathfinding lib will calculate a path between the unit’s current position and that 0th major waypoint.
  • This will provide a list of points that make up the actual path that the unit will follow. A line can be rendered along those points.
  • As more path calculations occur between the 0th and 1st major waypoint, then the 1st and 2nd major waypoint etc, the resulting paths (or legs between waypoints) can be added together to form a complete rendered path line to represent the path the unit is following. As the unit tracks through each waypoint of the mega-path, the rendered line is cropped so that it only renders from the current waypoint up to the up to the final destination waypoint.

Touch-dragged paths

The above steps work great if the major waypoints are well defined all at once. Consider a modern RTS game where you can shift-click out a bunch of waypoints for the unit to follow; when you release the shift-key and mouse press, the path that navigates through all the major waypoints is created in one go.

This isn’t applicable for touch screens. Games like Flight Control have created the expectation that the unit will move as soon as you start dragging. The problem with this is that the drag motion creates a huge amount of points which need to be filtered. It would be a bit of waste of processing power to feed the pathfinding lib a multitude of paths to work out.

Here’s what is going to happen:

  • The user starts dragging and the pathfinding lib calculates between the unit’s pos and the drag point.
  • The user continues to drag and x number of major waypoints get detected. This is where things get a bit crazy…
  • …The pathfinding lib does its processing in a background thread and a callback notifies when it’s done processing each path. There’s a chance that many major waypoints have been added before the pathfinding lib has completed the path between the first 2 points it was given! This is an opportunity to do some resampling.
  • Take all the major waypoints from [targetMajorWaypoint, last major waypoint] and use the Douglas-Peucker Line Approximation Algorithm to resample those points to something that is a lot simpler (less points).
  • This creates a complication for our rendered line. It now comprises of both the calculated paths that the library has processed and the remaining resampled points that make up what the user/player has drawn on the screen.

Pathfinding errors

Ignoring the obvious z-fighting issues, there is one glaring problem and it partly from trying to interpret user intent. I’ve drawn a path that goes through the middle of the buildings but because of the amount of major waypoints being recorded and the resampler not taking enough points away, some of those major waypoints have ended up in the streets between buildings. The result is a u-curve path around buildings as the pathfinding lib calculates a path from one side of the building to the other. A much simpler path is required, certainly not one with u-curves in it.

Consuming the line

The last piece of the puzzle is the rendered line being consumed. There is one giant issue that occurs when the distance between two waypoints is quite large. As the unit starts moving toward the next waypoint, the line segment/leg between the previously reached waypoint and the target/destination waypoint is “consumed”. A suddenly disappearing line segment is going to be really obvious to the user. I see a couple of solutions:

  1. Resample the rendered path so that there are even more points; essentially subdividing each line segment of the path. This new line should probably exist as a different list of points but because this subdivided path perfectly maps on top of the path the unit is following, the unit will transition through each of the multitude of points of the rendered line. A distance check between the unit and each of those points making up the line will dictate when the segments are lopped off.
  2. Alternatively, the line segment/leg that the unit is currently following could become semi-transparent. In fact, the amount of transparency could increase the closer the unit gets to the next waypoint. This could look quite good.
    1. Advertisements

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