Unit Pathing and range highlighting

Hi guys,
Two fairly simple to implement features that would have tremendous impact on gameplay:

1. Unit pathing -> select a unit, select target, unit will automatically calculate shortest path.
Implementation: simple A* on the terrain with cut-off at max unit range (only hit when the point is unreachable).
Why does it help: Moving through tight spots is a huge pain when each turn has to be manually executed. This saves a lot of micromanagement when moving ships around islands too.

2. Real unit range highlighting -> select a unit, only the terrain it can actually reach is highlighted (instead of the circle). IE water will not be highlighted for tanks etc.
Implementation: (not sure how drawing's done in silverlight) similar to pathing, start moving out from the unit position and change pixel colour if it can be reached from the previously checked position. Cut off at unit range.
Why does it help: It is much easier to understand the terrain when you can see where the unit can get,

(this assumes your playing area is divided into a grid of spots that have well defined neighbours, but it should be adjustable for continuous spaces too).

I know both areas are fairly simple, and might have been suggested before. Search didnt find anything though.

1st one I like, but sounds quite difficult to implement, seeing as it sounds like you would have to implement some sort of CP or AI to calculate the course to the unit you wish to attack, 2nd one is a bit meh, I honestly think the good 'ol circles are just dandy.

#1 is good, double click where a unit cannot reach and it will automatically calculate?

#2 is also good, however I suggest a circle where land that cannot be reached (sea for ground units) will become red and the rest green.

I think the ideas are good in thought but not worth the amount of work it would take to put in to it. The idea of automated movement has been suggested a couple of times and it's definitely a good idea but obviously difficult to implement. The way I could see it working is to just allow you to move a unit and then click it again and lay out your moves for the next turn. Still probably very difficult to create.

I enjoys playing naval camander alot and find alot of the problems you mention to cost me the valubale 120seconds i need to take my turn. Expecialy around areas like denmark.
I have also suggested simmalar changes you are propsing
A 3rd and easy change would be to raize the zoom lvl for the game so that the conjested areas become bigger on the screen. if i could zoom to just denmark sized area it would help me combine my forces and move my ships much faster.
This increased value of zoom would also prepair the game for later graphical upgrades. IE terrain.
i vote Yes to both proposals and would use them alot.

To gig: there are a ton of programs out there that have an auto move coded into them there must be something you can use as a platform.

No offence, but me an Amok laughed a lot at the phrase "Two fairly simple to implement features" - this is really a gross understating of the task involved. There are no paths in the game, everything is coordinate-based. Silverlight is not a proper gaming engine and doesn't have any built-in modules to help out. It just draws vector objects based on your coordinates, that's all.

Both proposed features are in the 'nice-to-have' category, but hardly indispensable. Implementing them, however, is close to impossible.

Are the coordinates discrete or continuous?

For discrete coordinates:

Unit pathing is a trivial dijkistra with the straight line distance as your heuristic, weight of edge A-B = distance between A and B if this unit can go from A to B, +inf otherwise.
Range highlighting: on clicking the unit, take its position x, highlight it, for all neighbours of x that can be reached from x by this unit, recurse with range of the unit decreased.

For continuous coordinates, discretize them into small squares (must be about 1/3 of the size of the smallest natural 'choke' to guarantee a path will be created if possible) and continue as before.

All of this is of course done client-side, without involving the server at all, so any computation effort can be considered 'free'.
I know there might be other considerations making it impossible to implement, but lack of paths and pre-built modules is not one of them.

I'm not sure what you mean by discrete / continous coordinates. Our map is vector-based, it consists of paths which in turn consist of points. You will have to take into account all these points (there are A LOT), and hit test them with every mouse move. Silverlight will never let you do that without completely degrading the performance. And even if it did, there still needs to be some kind of algorithm to calculate the path, which is not worth the time it takes to implement. Same applies to range highlighting.

I've done some programming a long time ago (year 1988 to 1995)
The vector map doesn't seem to me able to implement any path calculation.

A new layer with paths woud be mandatory, a big work.

Balancing this game, and keeping it as simple as it is, will be a good thing.

For the turn time, I know the "young" (sorry no offense, just meaning I'm a bit older) like quick games, our social environement is quick and fast now.
But the old paper wargamers know that moving units takes time.

You don't need to consider *all* the points. Start from where the unit is, check all the neighbouring points. You check at most the whole range radius of the unit, usually much less - in the case a straight line can be drawn, you only check the points along the line.

So in pseudocode, mostly stripped from wikipedia A* algorithm:
http://pastebin.com/8iDwRtQ3

This will :
- only test the points on the straight line if straight line is possible - no performance penalty in 99% of cases
- only test the full circle of points in *range* radius when no path exists - manageable penalty?
- always find the shortest path if the path exists and has lenght < range

The discrete/continuous thing is simple: is there a pair of two points such that there is no 'point' between them - i.e. neighbours. If yes, your map is discrete. If not, your map is continuous. So if your coordinates are integers, your map is discrete, if they're floats, your map can be either discrete (if there is some smallest distance between two points) or continuous - given any two points, you can always find a point in between them.

Four more things:
1. There is no easy or fast way to find out if a specific point of the map paths is bordering with the water.
2. Last time I checked, Silverlight doesn't even allow you to get a collection of points in path. You can get a text representation of it, but not the actual numbers. Parsing the text is not the fastest thing.
3. Even within the unit movement radius, there can be thousands of points, which you'll have to check with every movement of the mouse, this will definitely degrade the performance. Don't forget that while searching for the shortest path you'll often come to a dead end and will have to start all over again - things like this will also slow it down.
4. Although we don't use them at the moment, in a path there is a possibility to use curves instead of a straight line, and curves are very hard/slow to calculate.

These are just a few things that came to mind. As you can see, it's not as simple as it looks.

Skrevet av Anderkent, 16.03.2011 at 09:18

This will :
- only test the points on the straight line if straight line is possible - no performance penalty in 99% of cases
- only test the full circle of points in *range* radius when no path exists - manageable penalty?
- always find the shortest path if the path exists and has lenght < range

Before performing the calculation you could see if the target is within you're range.
And then after that you could make sure that there is at least one tile next to it that you can move onto.
So you're idea is good.

Do you program Anderkent? I guess you must to know Dijkstra and A*.

But the game isn't tile based, which would make those algorithms the obvious choice.
It's really not practicable to use those pathfinding methods on pixels either, especially since you would need to check which pixels each unit/city is on. The cities would set what pixels they're on at compile-time, and the units would set their pixels at run-time.
For something like this I wouldn't put it in one big array, there wouldn't be an element for each pixel.
Instead, I might create a list of objects that tell which pixels are being used. One per game element (city/unit).

That's off the top of my head, and not the point, because what happens when the game is resized? Pixels are lost and the entire thing would have to be recalculated based on the new pixels. I suppose you might be able to keep the old calculations if you decide where those new pixels are and scale them...

Figuring all of that out (unless there's a way somebody else sees) doesn't seem worth it so you don't need to manually move your guy around in tight spaces.

I was going to suggest looking up ray-trace pathfinding, but then realized it also doesn't really seem worth it and would be too expensive anyways.

Skrevet av AdmittingZero, 16.03.2011 at 11:58

but then realized it also doesn't really seem worth it and would be too expensive anyways.

Exactly.

Well, it's your call of course. I feel like you still need to check exactly the same amount of points when checking if a straight path for a tank does not cross water/defenceline/etc. So using a* should not degrade performance significantly there.

I guess I still misunderstand how the current map/movement works. I need to take your word for it here, since there's no code available (right?).

Skrevet av Anderkent, 16.03.2011 at 12:40

Well, it's your call of course. I feel like you still need to check exactly the same amount of points when checking if a straight path for a tank does not cross water/defenceline/etc. So using a* should not degrade performance significantly there.

I guess I still misunderstand how the current map/movement works. I need to take your word for it here, since there's no code available (right?).

Yep, we're not planning to release the source code.

Skrevet av Amok, 16.03.2011 at 13:15

Yep, we're not planning to release the source code.

.NET Reflector...

Skrevet av Ivan, 16.03.2011 at 02:24

No offence, but me an Amok laughed a lot at the phrase "Two fairly simple to implement features" - this is really a gross understating of the task involved. There are no paths in the game, everything is coordinate-based. Silverlight is not a proper gaming engine and doesn't have any built-in modules to help out. It just draws vector objects based on your coordinates, that's all.

Both proposed features are in the 'nice-to-have' category, but hardly indispensable. Implementing them, however, is close to impossible.

It seems like everything is too hard to implement...is silverlight realy that hard to work on?

Skrevet av AdmittingZero, 16.03.2011 at 13:35

.NET Reflector...

True. Though the code is partly obfuscated, so it will be a bit more difficult.

Skrevet av Garde, 16.03.2011 at 13:46

It seems like everything is too hard to implement...is silverlight realy that hard to work on?

We're not saying that everything is hard, just some specific things. Silverlight is the best technology for our purpose, without a doubt.

Skrevet av Amok, 16.03.2011 at 14:00

Skrevet av Garde, 16.03.2011 at 13:46

It seems like everything is too hard to implement...is silverlight realy that hard to work on?

We're not saying that everything is hard, just some specific things. Silverlight is the best technology for our purpose, without a doubt.

Gardevoir: the pathfinding isn't hard because it's Silverlight, it's essentially the same steps in ActionScript 2.0/3.0, Java, C#, Python etc. just different syntax. The reason it's hard is because the game isn't tile based; which is what A* and Dijkstra rely on to work. You can use those algorithms for a game that's not visually tile-based, but you'll still need to construct some sort of data structure to search through.

It's especially hard in this scenario because the map would likely need to be constructed by hand (visually moving points around) and making connections between those points.

Sitat:

We're not saying that everything is hard, just some specific things. Silverlight is the best technology for our purpose, without a doubt.

Well silverlight seems nice, but from how ive seen it too many good things can't be done on it, but hey, at least it's not flash...that would be a nightmare.

Skrevet av Garde, 16.03.2011 at 15:08

Well silverlight seems nice, but from how ive seen it too many good things can't be done on it, but hey, at least it's not flash...that would be a nightmare.

Silverlight is certainly the best platform for web game development at the moment.

Sitat:

Silverlight is certainly the best platform for web game development at the moment.

Well hey, I wouldn't know. I don't make games I sell them...and records. But from what ive heard HTML5 is supposed to replace silverlight once they release it.

Skrevet av Garde, 16.03.2011 at 15:08

Well silverlight seems nice, but from how ive seen it too many good things can't be done on it, but hey, at least it's not flash...that would be a nightmare.

Most of the things that can be done with Flash can be done with Silverlight. You also have the custom .NET libraries (not full .NET for security & size for starters) which gives you a lot of clean (and previously documented/used) functionality AND you can write Silverlight games in any language that will compile to the CLR. That's about as technical as I can get about it before being wrong lol. It means that programmers with traditional backgrounds in C#, Visual C++, VB.Net, and much much much more can write Silverlight games. The first version of Silverlight even allowed you to write Silverlight games in JS (which I'd be surprised if you can't do anymore when compiling to SL 4).

ActionScript 2 (Flash) was my first programming (technically scripting) language. Then I moved to AS3, it's really not a nightmare at all. There's a reason for it's deep market penetration and extensive amount of content. It's crazy popular and easy to get into.

Now...

Skrevet av Garde, 16.03.2011 at 15:29

Sitat:

Silverlight is certainly the best platform for web game development at the moment.

Well hey, I wouldn't know. I don't make games I sell them...and records. But from what ive heard HTML5 is supposed to replace silverlight once they release it.

HTML5 is supposed to replace Flash, Silverlight, and Java Applets... I doubt it would displace Web Unity3D; I'm not even aware of any sites or portals with Unity games. On second thought, Kongregate supports Unity.

You say "they", it's not any company, HTML5 is just a standard - what the W3C decide that the internet should be like really... I think the specifications for many HTML5 and CSS3 for years now. All modern browsers have been slowly implementing those specifications, none have them all down, and none are 100% compliant. You'll see a lot of people flaming Microsoft for that. IE has been in the past, famously non-compliant.

There are some good HTML5 games out there already, and Adobe (they own Flash) has released a tool to convert Flash animations to HTML5. But the problem with HTML5 games right now is that they tend to only work well on one or two browsers of the major ones (IE, Firefox, Chrome, Safari and I guess Opera). Each of them have their quirks and needs. The browsers need to become compliant before HTML5 can take off.

Microsoft may well stint IE9's compliance so that Silverlight continues to be a favorite, but I doubt it. Instead, I bet Silverlight will become a favorite for it's new Windows Phone products and maybe eventually other cell phones (replacing Java).

Flash on the other hand doesn't have such an easy way out, it'll probably have to fight HTML5 hard to survive.

I'm not sure if it's possible but what if you put a white/black map layer, where white is the walkable paths for units and black the walkable paths for sea

This layer would be used to show where a ground unit can walk and where a sea unit can walk by using this map to show with the movement circle what unwalkable is (red) and what walkable is (green)

WOW this is complex sounding. are you saying increasing the zoom size for the map would require a huge amount of work? that alone would make it somewhat easyer to move troops?

I was just going to let Amok reply about how practicable that would be... but I guess for whatever reason he hasn't (maybe hasn't seen it etc.)

Yikha: It very much seems that this is basically what they're already doing to determine where a sea unit and land unit can move to.
There is already, as I'm sure you're aware, a green circle that shows up when you start dragging on a troop to show his movement range. Are you saying that they should cut out the parts of that circle that can't be walked on? Like if you're near lakes... Or the sea or something?

It's definitely very possible, but very dependent on how they set up their map and collision detection system. If it doesn't immediately work with what they have I wouldn't expect them to change it for that...

Urlander: Zooming in should not be a problem; and they have already created a great zooming system. I can't think of any technical reason why they couldn't let you zoom in even more. I assume that the current max zoom level is the most comfortable level for most play.

Skrevet av AdmittingZero, 18.03.2011 at 01:37

We're using built-in Silverlight HitTest method on our main map layer (not black/white).
Cutting the parts of the circle that can't be walked on is almost impossible in SL.
Increasing the zooming level is not a problem, but you'll get blurry texture in that case, and I don't thing it's really needed.

Well instead of cutting parts away from this circle, highlight the unwalkable parts red and the walkable parts green, is what I am suggesting

But would that be possible with "HitTest" ?

I guess only a second layer can make this possible?



If it is, then would it be useful to have such thing? I think it does, since you can more easily move your troops this way, in the fastest way possible.

Skrevet av Yihka, 18.03.2011 at 10:46

Well instead of cutting parts away from this circle, highlight the unwalkable parts red and the walkable parts green, is what I am suggesting

But would that be possible with "HitTest" ?

I guess only a second layer can make this possible?



If it is, then would it be useful to have such thing? I think it does, since you can more easily move your troops this way, in the fastest way possible.

Sadly, Silverlight doesn't have a proper drawing API. It's still theoretically possible to do this with what it offers, but it be unbearably slow, and will take a lot (and I mean a lot!) of time to implement. So there's no second thought on this, really.