I had an idea related to waypoints, unit control, and to a lesser extent pathfinding (specifically in RTS & RPG games but it could probably be applied elsewhere) that I''d like comments/criticism on. Forgive me if this is old news but I haven''t heard of it being done before and searches in the forums were fruitless (filtering through 8 million posts without a specific term to look for is... mind numbing at best). When you give a movement command in most RTS & RPG games it''s generally either by specifying a final position or a series of waypoints leading to a final position. The game is then supposed to find an optimal path to the endpoint via the intermediate waypoints, if any. The problems I see with this from both the designer/programmer and player perspectives: - Computationally expensive pathfinding algorithms - Cheapest path isn''t necessarily a ''smart'' path in terms of avoiding danger (or other criteria) - Units moving in groups often split up when going around large obstacles and make themselves vulnerable - Entering multiple waypoints can be tedious (lots of shift clicks in many implementations I''ve seen) - Paths aren''t smooth I can think of others, those are just a few examples. Wouldn''t it be easier if the player used the mouse to "draw" a smooth path that he wanted units to follow? You could simply save a bunch of points on the path he draws, or even use those points to generate a spline and create as few or as many waypoints along it as you want. You could then use some simple steering behaviours to work out the details of following the path (keeping groups together, maneuvering around small obstacles, units avoiding each other). As far as advantages, this basically helps eliminate a lot of the problems I mentioned above: - Easier for players to input not only multiple waypoints but also an exact path to follow - Eliminates some of the need for pathfinding algorithms - Prevents the AI from choosing cheap but stupid paths This system won''t always be practical of course: - It''s often convenient for the player to just give a destination and not an entire path - If you don''t allow zooming of the player''s view then the path he can draw is limited to the size of the view area (simple solution: allow zooming heh) - Players could sort of break the system by drawing a path straight through a large object, or a concave object (isn''t this true of many pathfinding algos?) I think you would have to use some combination of this method and standard pathfinding to create a reliable system. Thoughts? Do games already do this? (sure haven''t seen any) Is it totally impractical for reason X? And so on.

I think making users specify the entire path will get a bit tedious. Especially for an RTS where issuing movement commands is pretty much what most RTS'' are about (perhaps that''s a design issue though).

If you can make your path finding smart enough to avoid enemy units (not difficult, most algorithms can take a "path cost" into account, just make a path that goes past an enemy of higher cost than normal), and quick enough (not that difficult, if you''re clever about it) then what''s the problem.

The real difficulty is making your units act realistically. If you can''t see an area of the map, your unit shouldn''t try and go through that area. And if you tell them to move to an unexplored area of the map, they shouldn''t just find the quickest route straight off like that. But the solution isn''t to make the user specify the path themselves. Most games try to move away from micro-management as much as possible (though it can be fun sometimes, I think this is taking it a bit too far).

codeka.com - Just click it.

quote:Original post by walkingcarcass
have you ever used a drawing program where you click a start point and as you drag the mouse, a best-fit lin between colours, highlights and shapes is calculated?

suppose the interface is like this: you click a start point, you move the mouse and a line is drawn that avoids obstacles and hazards, when you click the mouse again, that path is set and the next line is generated and updated as frequently as you move. then eg double-click to end.

this has the advantage of seeing what is acceptable before it is used, and clicking many close points if you want to command a high level of control in tricky situations.

Never seen anything like that, interesting.

quote:Original post by Dean Harding
I think making users specify the entire path will get a bit tedious. Especially for an RTS where issuing movement commands is pretty much what most RTS'' are about (perhaps that''s a design issue though).

Near the end of my post I said I don''t see this as a complete replacement for normal pathfinding, more as a complement to it. Certainly in some situations you don''t care what path is taken and you just want to click a destination, but sometimes you want more specific control. Is it really that tedious to hold down a mouse button and draw a quick curve on the screen? Is drawing a line in a paint program so hard? If you have to do it for every single movement command for lots of individual units then yes, but that''s not what I''m suggesting.

quote:If you can make your path finding smart enough to avoid enemy units (not difficult, most algorithms can take a "path cost" into account, just make a path that goes past an enemy of higher cost than normal), and quick enough (not that difficult, if you''re clever about it) then what''s the problem.

I know A* and similar algorithms take path cost into account, but it''s usually something static and simple, like rough terrain vs flat terrain. If you try to account for enemy threats you''re going to add all sorts of complexity:
- Enemy units are constantly moving so you have to reevaluate the threat they pose after every game step
- Danger a unit poses isn''t a simple thing to calculate, you have to take into account a) whether the enemy unit actually has the ability to attack (eg ground unit with no AA against a jet) b) relative speed c) enemy''s attack range d) enemy''s visibility range and line of sight e) attack/defense strengths
- You need to provide a mechanism for the player to tell the pathfinding algorithm "don''t avoid enemy units" for the case where he really does want to engage the enemy.

quote:
And if you tell them to move to an unexplored area of the map, they shouldn''t just find the quickest route straight off like that.

Yes, that''s a pet peeve of mine from Starcraft, I assume lots of other games do it too.

quote:But the solution isn''t to make the user specify the path themselves. Most games try to move away from micro-management as much as possible (though it can be fun sometimes, I think this is taking it a bit too far).

I don''t really see this as micromanagement. A commander in battle will sometimes say "go to waypoints 4,8" or whatever, but sometimes it will be "go to waypoints 4,8 via the left flank" which is very different. So as I see it this system is good for giving semi-complex movement orders to groups of units. NOT individual units, that would get extremely tedious and would be stupid micromanagement. Maybe this isn''t a great system for a typical RTS but I think it would have real advantages in a more tactical combat oriented one (something like Myth). You can quickly give out orders to execute a pincer attack, flanking maneuvers, or whatever.

It could be practical on an RTS if the minimap was big enough for you to do it to some degree of accuracy. It would be too tedious to use on the main map much of the time, although I can see the benefit in RPGs if you wanted to avoid a trap for example.

Plus, your approach doesn''t quite solve everything that you imply that it does. What if the player draws a smooth path that happens to pass over a single obstacle? Reject the whole path? Or do traditional pathfinding around it, thus potentially damaging the ''smooth'' aspect? Plus, there''s no reason traditional pathfinding can''t generate smooth paths - it''s all about how you choose successor nodes in the search space. And I don''t really see how it helps group movement any more than a traditional method does. What if I draw a line across a narrow footbridge? Do all the accompanying units flock around the sides and fall off? You''re still gonna need a lot of intelligence when it comes to following that path.

I think the only benefit here - although it is a very large one! - is to be able to specify the exact kind of route you want the unit to take. I think all the normal pathfinding caveats will still apply, except the player need never be surprised or annoyed at the computer''s choice of path.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files ]

quote:Original post by Kylotan
It could be practical on an RTS if the minimap was big enough for you to do it to some degree of accuracy. It would be too tedious to use on the main map much of the time, although I can see the benefit in RPGs if you wanted to avoid a trap for example.

Coupling it with a zoomable view, as I suggested in my original post, might overcome this somewhat.

quote:Plus, your approach doesn''t quite solve everything that you imply that it does. What if the player draws a smooth path that happens to pass over a single obstacle? Reject the whole path? Or do traditional pathfinding around it, thus potentially damaging the ''smooth'' aspect?

Provided the obstacles are relatively small/simple, I think a simple steering behaviour for obstacle avoidance might do the trick. I should probably put together a little demo to test it out.

quote:And I don''t really see how it helps group movement any more than a traditional method does. What if I draw a line across a narrow footbridge? Do all the accompanying units flock around the sides and fall off? You''re still gonna need a lot of intelligence when it comes to following that path.

I meant more in the sense that you give an explicit path for a whole group to follow so you don''t have to worry about the AI in the background choosing different individual routes. Crossing a narrow bridge is still a problem, but this gives me hope.