Rally Points

[vts]

Greetings -- I'm new to the 0 A.D. community, I can do some programming and I have some spare time on my hands, so I figured why not see if I can help out. So for the last week or so, I've been working on getting this ticket fixed: Render marker line between building and rally point. With a lot of help and patience from the kind people on IRC, I've now reached a point where I think it would be useful to get some feedback from everyone to hear your opinions on the contributions I have to make and whether I did it right.

So here's how it looks. For testing purposed, I've been using a very simple black and white texture for the path, but any texture/color can be chosen -- this is just a placeholder. Ideally rally point paths should be visually unobtrusive, but clear enough to be noticed. Ignore the red outline by the way, that's an unrelated debug overlay.

More imagery available at:

http://i.imgur.com/fGNOT.jpg

http://i.imgur.com/D1K0t.jpg

http://i.imgur.com/pjHRw.jpg

Since people seem to enjoy details of how things work, here's the way the rally point path is currently constructed:

1) First, the long-range pathfinder is used to grab a tile path from the building's center to the rally point. This path is zig/zaggy, so every two adjacent points are averaged to reduce zig/zag staircases to straight lines.

2) Next, waypoints within the building's footprint are removed. The point on the edge of the footprint that is closest to the (then) first point outside of the footprint is found and added back as the end of the path (the pathfinder actually returns the path in reverse order, from goal to start).

3) Next, the path is smoothed using spline interpolation.

4) Next, a textured overlay line is created to draw out the interpolated path.

5) Finally, end caps are optionally added to the textured overlay line to make the endings looks prettier.

For the spline interpolation and textured overlay, I was able to reuse Philip's original code for the territory outlines, albeit slightly modified to also allow for open paths. Because open path endings don't look very good, I also implemented some line cap ending options, similar to those you would find in e.g. Illustrator. Here's how it looks without line caps:

And here are the three available cap options (round, square and sharp):

In each of these cap endings, the texture's left vertical edge is curved around the rim of the cap, so one requirement to use these caps is that the texture is symmetric, otherwise one of the edge points where the cap is attached will look weird.

All of the line's settings (texture/color/width/line cap endings) are configurable through XML. There are still some issues to iron out:

1) I would like to see the rally point path use straight line segments as much as possible, which make more sense to the user than a mathematically (near)-optimal but visually curvy path.

2) The rounded line cap endings are kind of funky on hills. The square caps are much simpler in code and behave much better on difficult terrain, so I might just simplify the rounded caps.

3) Someone added a bunch of different rally point flag textures for each civilization as actor variants a while back (I forget who), but it doesn't look like they can be selected yet, so that should probably happen once those are working.

-----------------------------------------

On the first picture, you'll also notice the extra button I added to focus on the rally point, as requested in the ticket. Clicking this button will instantly take you to the rally point, or, if no rally point is set, to the building itself.

Again, for now I've used this temporary crosshair image. I went with a single-click button rather than double-click as requested in the ticket, because frankly I don't know how :]

-----------------------------------------

Along the way, I encountered a few issues that I think would be interesting to discuss.

1) Because the long-range pathfinder is used to find the initial path, it will happily curve around terrain and buildings in the SoD. This could potentially enable players to find out details about areas that they shouldn't know about. One option would be to hide the rally point path under the SoD, but that sort of defeats its purpose. Another option suggested on IRC was to follow the pathfinder waypoints up until the edge of the SoD, and from there continue in a straight line to the rally point, maybe in another color or dashed or something so that the difference is visually clear.

2) Currently it is possible to set a land building's rally point in the middle of the ocean. Created units will walk up the shore and come to a halt, which begs the question: is it useful to be able to set a land building's rally point on water? Should we limit it to within a particular range around the shore or something? The reason I ask is because the pathfinder will stop at water edges when started from land, so if the rally point is far out into sea, the (interpolated) waypoints on water will be spaced disproportionally far apart which creates jaggy segments and just doesn't look good.

Edited August 1, 2011 by vts

[Pureon]

I've been following your progress on IRC these last few days and it's great to see you've worked out most of the issues

1) Because the long-range pathfinder is used to find the initial path, it will happily curve around terrain and buildings in the SoD. This could potentially enable players to find out details about areas that they shouldn't know about. One option would be to hide the rally point path under the SoD, but that sort of defeats its purpose. Another option suggested on IRC was to follow the pathfinder waypoints up until the edge of the SoD, and from there continue in a straight line to the rally point, maybe in another color or dashed or something so that the difference is visually clear.

A dashed straight line starting at the beginning of the SoD sounds good to me.

2) Currently it is possible to set a land building's rally point in the middle of the ocean. Created units will walk up the shore and come to a halt, which begs the question: is it useful to be able to set a land building's rally point on water? Should we limit it to within a particular range around the shore or something? The reason I ask is because the pathfinder will stop at water edges when started from land, so if the rally point is far out into sea, the (interpolated) waypoints on water will be spaced disproportionally far apart which creates jaggy segments and just doesn't look good.

Could the rally point automatically change to the nearest accessible piece of land (so where the unit would stop anyway)?

How does it look when the rally point is behind a wall stopping the unit from reaching the desired spot?

[Mythos_Ruler]

Yeah, I like the dashed line better, possibly with more transparency, so it can't be confused with a territory border. I also like the "arrow" terminus of the line.

It would be good to have this implemented for units as well.

All-in-all, awesome work!

[aldur]

why don't you draw "footprints in the sand" instead of a black-line.. would make sense for me

[ribez]

why don't you draw "footprints in the sand" instead of a black-line.. would make sense for me

cool idea, but probably a simple line could be more visible at every zoom level

[vts]

Could the rally point automatically change to the nearest accessible piece of land (so where the unit would stop anyway)?

That would be where the pathfinder calls it quits, so that should be easy enough.

How does it look when the rally point is behind a wall stopping the unit from reaching the desired spot?

If there is no path from the building to the rally point (according to the long-range pathfinder at least), then no line will be drawn. The rally point flag may still be there though, so I'm not sure if that's the desired behaviour.

Edited August 2, 2011 by vts

[Jeru]

Can anyone record some video of this? I would like to integrate this in the release announcement of Alpha 7.

[Mythos_Ruler]

If there is no path from the building to the rally point (according to the long-range pathfinder at least), then no line will be drawn. The rally point flag may still be there though, so I'm not sure if that's the desired behaviour.

Perhaps a solid white line along the "walkable" path, then a broken line from the point where it is no longer walkable?

[Rasunadon]

Perhaps a solid white line along the "walkable" path, then a broken line from the point where it is no longer walkable?

Yes, and perhaphs it could see SoD/sea/no path as one problem: only dashed line there.

[vts]

Jeru - none of this code is committed yet, but I have Fraps so I could record a video of it if you like. Are you sure you want a video of it in its current state though? It's using just temporary testing textures for now, and the path is oftentimes still a bit too curvy too make sense. And if so, would you want a particular setting for the video, like an exit point of barracks during a battle or something or a will a basic one-building demo do? Also, I'd be interested to hear if anyone knows how to get smooth camera paths so the video wouldn't look jaggy.

[Jeru]

It's not urgent. There is a month or so until Alpha 7 is due.

Thanks, though.

[Ykkrosh]

I'd be interested to hear if anyone knows how to get smooth camera paths so the video wouldn't look jaggy.

The only way I know: Get Linux, and a PC-compatible Xbox 360 controller, then run xboxdrv, and put "joystick.enable = true" in the game's config file, then you can use the analog sticks to move and rotate the camera relatively smoothly. (Not a very widely applicable solution, though )

[vts]

Update; I've added some visibility checks between consequent waypoints, to reduce curviness from the pathfinder. The basic idea is that, as long as two waypoints have a straight visibility line between them, there's no reason to take any path between them other than a straight line. Humans don't walk from point A to point B by taking 10 curves along the way, they walk as straight as possible. Two points are considered to have a visible line between them if the 2D obstruction manager says that there aren't any obstructions between them, and if their terrain height difference is below a particular threshold. This allows for large straight lines on flat terrains, while at the same time keeping the keypoints close enough to get a smooth line on hills and slopes.

I also fixed an interpolation issue that caused funky curved endings on either side. Here's an old vs. new comparison:

The new image has debug overlays turned on; the red circles are keypoints, the white ones are interpolated points. For starters, you can see that the path is a lot more like the path an actual person might walk. As you can see, the lower keypoint in the S-curve around the rock in the old image was eliminated, producing a more straightforward path along the rock. Also, the line ends in a nice straight ending instead of curving at the last minute. The nice thing about this is that slightly moving the rally point will only change the curvature of the last segment slightly, as you would expect.

Here's another image showing how the path is made to be more straightforward instead of sticking to the edges of obstacles:

And just for fun, here's an image showing the elimination of consecutive keypoints on flats while maintaining them on slopes:

All in all, I think it's an improvement. Thoughts?

Edited August 3, 2011 by vts

[Jeru]

Big thumbs up.

[Mythos_Ruler]

Hmm, are you updating the actual pathfinder? Would look goofy to have a visible path line that the units don't actually follow. (the path line is straight, while the actual pathing is curvy).

[vts]

Hmm, are you updating the actual pathfinder? Would look goofy to have a visible path line that the units don't actually follow. (the path line is straight, while the actual pathing is curvy).

I'm not touching the pathfinder, I'm merely editing the path it produces. Although I agree that it would look goofy to have a visible path that units don't actually follow, this is currently not going to happen anyway because units are spawned at randomly-picked locations around the building. On top of that, unit movement is controlled by the short-range pathfinder, which only uses the long-range path as an incremental guide to compute its own (more detailed) path, so from the get go there's really no guarantee that a long-range path will be representative of actual unit movement.

Edited August 3, 2011 by vts

[Mythos_Ruler]

Ah, makes sense. Carry on, explorer!

[feneur]

This is starting to look really sweet And while it may not be an exact representation of the actual path a unit will take, it's sure going to be helpful to have a general idea. Maybe you might want to change the point slightly if it goes too close to an enemy, or if it's for say a barracks where you're going to have units come out and go to the rally point for a long time you may want to cut down some trees which are in the way to make them go faster or something. Nice to have you post all this as well, really helps us to get an idea of what you're doing and all-in-all it's very interesting to follow. (Hope more people will follow your example )

[Chakakhan]

I think this a reasonable compromise in terms of matching up with the path finder. This looks really good!

[vts]

Still working on this, just really swamped with work right now. I've been editing the shaders to allow the rally point lines to be rendered inside the SoD and I've also added some generic code to create dashed lines.

A few issues remain which I'd like to discuss:

1) In the SoD, the idea was to render a dashed straight line from the edge of the SoD to the rally point itself so that the user doesn't get any information about the terrain or enemy buildings from the path. A problem however is that in the SoD, everything is still rendered, only entirely in black. That means the dashed rally point line can still be obstructed visually by black terrain and buildings at some camera angles. Without entirely rewriting the way the SoD is rendered (which I would not recommend), I suppose the best way would be to add a rendering pass that goes after everything else and which doesn't care about depth testing and whatnot so that it would just get drawn through any terrain inside the SoD or something.

2) Right now the long-range pathfinder is used to build an initial path which is then further post-processed. What should happen if a building gets placed smack in the middle of the rally point line? Do we ignore it or recalculate? I'd also be interested to know how to detect this in code, as I'm not yet very familiar with the internals of the pathfinder.

Edited August 14, 2011 by vts

[Ykkrosh]

Hmm, the hidden terrain thing sounds a bit annoying. Maybe it'd be fine just to have the line follow the terrain even in SoD? The terrain height in SoD is already not well hidden from players (they can e.g. use the camera zoom to detect hills and valleys, or click in SoD and look at the little animated movement-order confirmation symbol that we haven't added yet, or just modify the shaders if they want to cheat trivially), so exposing the same information through rally point marker lines (which is a pretty slow and unreliable method) wouldn't hurt much more. If it turns out to be a problem in practice and players exploit it, we can fix it then - it doesn't seem certain to me that it will be, so it's probably best to avoid the effort and complexity now and do the simpler terrain-height-exposing thing.

(I think it's more important to hide the existence of enemy buildings (especially walls) than the terrain, so it's probably still worthwhile having it stop using the full pathfinder data and doing the straight-line thing once it reaches SoD, even if it's still going to expose terrain data.)

Assuming the rally point paths get recalculated whenever the player selects a building in order to see its rally point path, I think it's fine to never update it automatically - players aren't going to look at it for more than a few seconds so it won't get very out of date, and if it does then they can just reselect the building manually.

(There isn't any way of detecting when a path becomes invalid (other than recalculating from scratch and seeing if it's the same) - it wouldn't be sufficient to check for buildings that are on the path, since destroying a building that's not on the path might open up a new shorter route and change the path.)

[Flamadeck]

Still working on this, just really swamped with work right now. I've been editing the shaders to allow the rally point lines to be rendered inside the SoD and I've also added some generic code to create dashed lines.

A few issues remain which I'd like to discuss:

1) In the SoD, the idea was to render a dashed straight line from the edge of the SoD to the rally point itself so that the user doesn't get any information about the terrain or enemy buildings from the path. A problem however is that in the SoD, everything is still rendered, only entirely in black. That means the dashed rally point line can still be obstructed visually by black terrain and buildings at some camera angles. Without entirely rewriting the way the SoD is rendered (which I would not recommend), I suppose the best way would be to add a rendering pass that goes after everything else and which doesn't care about depth testing and whatnot so that it would just get drawn through any terrain inside the SoD or something.

2) Right now the long-range pathfinder is used to build an initial path which is then further post-processed. What should happen if a building gets placed smack in the middle of the rally point line? Do we ignore it or recalculate? I'd also be interested to know how to detect this in code, as I'm not yet very familiar with the internals of the pathfinder.

The second one is easy.

Because there is a building, the units cannot go there.

Use the same thing you use when the waypoint is placed in an inaccessible area.

Just use two waypoint markers. One that tells the user where he places it and when that isn't reachable make it look different and add a second to where the units will be.

[Flamadeck]

Hmm, the hidden terrain thing sounds a bit annoying. Maybe it'd be fine just to have the line follow the terrain even in SoD? The terrain height in SoD is already not well hidden from players (they can e.g. use the camera zoom to detect hills and valleys, or click in SoD and look at the little animated movement-order confirmation symbol that we haven't added yet, or just modify the shaders if they want to cheat trivially), so exposing the same information through rally point marker lines (which is a pretty slow and unreliable method) wouldn't hurt much more. If it turns out to be a problem in practice and players exploit it, we can fix it then - it doesn't seem certain to me that it will be, so it's probably best to avoid the effort and complexity now and do the simpler terrain-height-exposing thing.

(I think it's more important to hide the existence of enemy buildings (especially walls) than the terrain, so it's probably still worthwhile having it stop using the full pathfinder data and doing the straight-line thing once it reaches SoD, even if it's still going to expose terrain data.)

Assuming the rally point paths get recalculated whenever the player selects a building in order to see its rally point path, I think it's fine to never update it automatically - players aren't going to look at it for more than a few seconds so it won't get very out of date, and if it does then they can just reselect the building manually.

(There isn't any way of detecting when a path becomes invalid (other than recalculating from scratch and seeing if it's the same) - it wouldn't be sufficient to check for buildings that are on the path, since destroying a building that's not on the path might open up a new shorter route and change the path.)

Then when someting changes how paths can be calculated, you could let that trigger the pathfinder and recalculate rally points?

[vts]

Then when someting changes how paths can be calculated, you could let that trigger the pathfinder and recalculate rally points?

Well that's kind of the problem. For clarity, the situation I was referring to is when you first place the rally points, and then some time later someone puts a building right along your rally point path. A sort of trigger like you mentioned would be perfect, but unfortunately I don't think there currently is such a thing. Nor do I think having it would necessarily be a good idea, as it all contributes to overhead to which pathfinding is already quite sensitive.

Edited September 11, 2011 by vts

[Sylvain Gadrat]

Just throwing an idea :

A big clue to know if the path may need to be recomputed is to check if the pathfinder modified it's abstract maps. It can be done by checking if "CCmpPathfinder.m_Grid->m_DirtyID" changed since last time you check it.

Note that it is not perfect :

- It is not triggered, you need to check periodically

- m_DirtyID is updated only if the pathfinder where asked to compute a path, so it can be unchanged while the line is invalid (until something ask for a path) (*)

- m_DirtyID can be changed due to a modification on the map not influencing your path

(*) Note, there is "CCmpObstructionManager.m_DirtyID" which is the same value except it is modified any time something change in the map. But it is private without accessor.

And finally : I like the solution to recompute only when the building is (re-)selected.

It is simple and will work very well in practice. Except, maybe, if you like to place rally points in middle of enemy territory and looking at the line during minutes.

My humble opinion : All that stuff seems to be very hacky. KISS, do it on building selection