FAQ Search
Memberlist Usergroups
Profile
  Forum Statistics Register
 Log in to check your private messages
Log in to check your private messages
Moonpod Homepage Starscape Information Mr. Robot Information Free Game Downloads Starscape Highscore Table
July-04: Path Finding With A*
Post new topic   Reply to topic    Discussion Pod Forum Index -> Developer Diary View previous topic :: View next topic  
 Author
Message
Moonpod Developer Diary RSS feed -RSS Feed
Fost
Pod Team
Pod Team


Joined: 14 Oct 2002
Posts: 3734



PostPosted: Fri Jul 09, 2004 3:34 pm    Post subject: July-04: Path Finding With A* Reply with quote

I'll split this month's diary into Battlescape|Starscape work, since we've ended up doing so much work on Starscape 1.5

BATTLESCAPE
Retextured the Cerberus to be more inline with the Hades. Many people on the board suggested it be a little more 'squat' so I played with the proportions of various parts and was happy with the final outcome, so kept it Very Happy
Cerberus MKII next to a Hades Heavy Tank for scale.

I'm currently in the process of texturing the 'Talos' Walking Tank variant.

The checker map is used to see if the mapping is distorted in any way - if you can keep all the checks roughly the same size, and perfectly square, then you should be able to make a nice, even applied texture for the model.

The main issue with these models is vertex count, rather than polygon count. Animated models in Battlescape use a framed model system. Rather than deforming the mesh based on a skeleton, I supply the game with a separate model for each frame of the animation, and the game morphs between each frame to create the animation. This type of system has been used quite a lot before (The Quake games use it for instance) and is very efficient, so should allow us to have more units on screen than any other system. Unlike static meshes however, some CPU processing has to be done for each vertex. So, the lower the vertex count, the better. It's important to seamlessly map and smooth (maintain single normal vertices) as much of the model as possible; any breaks cause the mesh to be split on export so it ends up with more than one vertex at the same position. We can also use some fairly modern techniques to accelerate the system such as vertex shaders, so high end cards can take advantage of additional speed increases.

Next month I'll have some shots of the Talos with all it's available equipment, and some downloadable animations its walk cycle.


STARSCAPE

The two main tasks for Starscape have been testing and minor changes for our Russian publishers. The Aegis status icons have always been a little ropey and we'd wanted to change them to icons for a long time. Since J(jump),F(fire),D(docking) don't necessarily work with their Cyrillic equivalents, and the letters are embedded in an image anyway (the rest of the text is sourced from unicode text files and so can be localised easily), now seemed like a good time to update them.
Also found time to add some new icons to the Warp Map.
We also received the Russian logo and put that into the game. Literal translation is 'Space Odyssey' Very Happy
and have been updating ship decals, such as the shuttle:
And the Aegis (or should I say Zeus Very Happy)


We've all been testing Starscape 1.5 day and night mainly this month. Sadly my "artist's eye" always picks out things when I'm playing the game that I'd like to improve on, and I'll stop for a second to add a few new effects to the game. This drives Poo Bear and Goober mad, because there's always a strong possibility it will introduce new bugs (as with adding any new content). Fortunately, the particles and effects system is pretty robust, and can handle even the error-laden effects definitions that I throw at it and point out to me what needs changing. Here's a few shots of things that I've tinkered with for 1.5:
Aegis ExplosionStar Boss Laser ContactOops!Mining Barge ExplosionInterdictor Explosion
I knew I should have put cannons on the Aegis... It took me ages to get this shot of the Starboss contact effect. I thought it would be fun to see it hitting the Aegis,
but the Aegis isn't really up to being hit full on by those lasers Very Happy
In fact, shortly afterward -- Goodbye Aegis Crying or Very sad A more appropriately sized explosion replacing the small puff of fire that we used to have.New interdictor explosion


Last edited by Fost on Fri Jul 16, 2004 11:27 pm; edited 6 times in total
Back to top
View user's profile Visit poster's website
Poo Bear
Pod Team
Pod Team


Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK



PostPosted: Fri Jul 09, 2004 3:56 pm    Post subject: Reply with quote

STARSCAPE
I spent the first part of last month ironing out bugs in Starscape ready for the 1.5 update, most of these are pretty minor as you would expect considering how long the game has been out. Sadly, the time taken to fix a bug is often inversely proportional to its severity i.e. show stopping errors are usually easy to fix, minor niggles take an age. Luckily I had some time left before the patch was ready and so I decided to go through the forum and see if there were any glaring gameplay issues coming up repeatedly.

A lot of people seemed to be finding some of the bosses and survival mode too easy so I spent a few days looking into that. Changing the way the game plays is fraught with danger, there can be knock on effects not readily obvious and properly testing something as complex as Starscape can take days. I have to be very wary when people say something is too easy as usually Internet forums are populated by hardcore players who are in the minority of your customers. In this case though I think they were right and so changes had to be made.

If you want to make something more difficult then the temptation is just to make the enemy's weapons do more damage and/or increase his armour. This is a pretty poor technique though and will soon result in the player getting frustrated. What people really want is a more sophisticated challenge. In this case that meant making certain enemies more maneuverable, adding more complex bullet patterns, requiring objects be destroyed in a certain sequence and adding more enemy units. Everyone seemed quite pleased with the end result.

We also prepared our final Russian version which is now being tested over at Snowball our publisher in that area of the world. Fingers crossed it gets through testing ok.

BATTLESCAPE
I've been looking (again) at the frightening spectre of navigation and at the back of my mind are the constant criticism of RTS reviewers who always seem to find something to complain about. It seems like nobody has ever made an RTS that worked correctly, why is that?

This problem is split into two parts a) path finding and b) unit coordination. Path finding is the easy bit (sort of), it's a solved problem. A long established algorithm known as A* (a-star) is the most efficient heuristic for calculating a path through any map. There are two problems with that sentence though:

1. heuristic - it means you are not guaranteed a perfect solution, what you'll get will be ok most of the time.

2. efficient - the algorithm is the fastest out there for getting the job done, but it is still horrendously slow in real terms. Analysing a map without any extra hints and clues is incredibly difficult to do quickly. Depending on the length of the path the calculation might take a very long time and the unit requesting it will just have to wait.

The end result is you must avoid requesting paths like the plague and even when you do get one there is a chance it will come across as fairly stupid to the player.
1: The green squares are a squad of 9 infantry men that have been selected and ordered up onto the hill.A* search algorythm phase 1
2: Each unit requests a path and A* immediately takes a direct line to the target position and drives head first into a wall.A* search algorythm phase 2
3: Like a blind man feeling his way through unfamiliar surroundings, A* widens its search and begins to back up looking for a way through. It might not look it but huge amounts of CPU power is brought to bear here as routes are built, evaluated and then discarded.A* search algorythm phase 3
4: Eventually A* stumbles on a way through the wall and gallops for the goal.A* search algorythm phase 4
5: A* made it at last, seeing this process in action should have programmers weeping over the huge amount of CPU time expended in this search.A* search algorythm phase 5

Unit coordination is the next part of the problem and it is the really interesting bit because it hasn't been solved. There is no text book holding a definitive answer and there are an almost infinite number of ways to tackle it. How should a group of units of different sizes, shapes, speeds and turning circles move together? What happens if one group walks headlong into another group? What happens if all this interaction is taking place in a narrow ravine with no room for manoeuvre? Who moves first, who stops, who gets out of the way and who barges through? Oh and don't forget, please don't ask for a proper path unless you absolutely have to.

So I can certainly understand now why no RTS has ever really managed to get it perfect, maybe they never will. Still, the player is still right to demand perfection, after all there is a war on and we don't want our soldiers wandering about like fools.
Back to top
View user's profile Visit poster's website
Goober
Pod Team
Pod Team


Joined: 11 Oct 2002
Posts: 449
Location: Moonpod Central



PostPosted: Fri Jul 09, 2004 3:59 pm    Post subject: Reply with quote

This post intentionally left blank.






















(I was working on Starscape 1.5, so no interesting Battlescape news from me I'm afraid. I'll have something cool for next month though)
Back to top
View user's profile
HunterXI



Joined: 26 Dec 2003
Posts: 476
Location: Playing like there is no tomorrow.



PostPosted: Sun Jul 11, 2004 12:40 pm    Post subject: Reply with quote

It takes a lot of CPU power to do path finding? I had always thought that path finding was incredibly difficult to code, but was pretty efficient...

I would think that what the unit should do is see if he can go straight there. if he can't, create an ever-expanding circle around his destination until that circle reaches him... ah well, I dont really know what Im talking about, but I'll try and think of intelligent ways to do it without serious CPU power... Blizzard did it Smile
Back to top
View user's profile
Bobacles



Joined: 17 Mar 2004
Posts: 123



PostPosted: Sun Jul 11, 2004 9:29 pm    Post subject: Reply with quote

Is it possible to have the major paths figured out when the map is compiled? The map itself would keep track of important things like open areas, and the choke points that separate them.
Back to top
View user's profile
Poo Bear
Pod Team
Pod Team


Joined: 14 Oct 2002
Posts: 4121
Location: Sheffield, UK



PostPosted: Sun Jul 11, 2004 9:52 pm    Post subject: Reply with quote

You can scale your map down, half the size each time. Smaller maps obviously search faster but carry less detail. So you work out a rough route on the scaled down map and then use the full scale map to find small paths between these points.

You can partition your map into navigable regions and isolate the navigable connections between them. Besides speeding up path finding this information can be used by more advanced AI routines to work out good places to attack you (i.e. choke points).

Age of Empires (among other games) uses both these techniques.

Whether we will use them or not I'm not sure, they aren't a "silver bullet", in some rare situations they can take longer to find a path than a normal A* would, they complicate the code and they can also lead to more stupid looking paths.

Without them, as the number of units starts to grow, as maps start to grow, as PC specs shrink you start having to cut short path searches and take "best fit" solutions that can also lead to stupid looking paths. More experimentation required I think.
Back to top
View user's profile Visit poster's website
Harabek



Joined: 10 Apr 2004
Posts: 94
Location: Arkansas, yes we have computers.



PostPosted: Mon Jul 12, 2004 7:52 pm    Post subject: Reply with quote

Wow this stuff is looking great.






Good work
Back to top
View user's profile
Johnh



Joined: 06 Sep 2003
Posts: 160



PostPosted: Tue Jul 13, 2004 9:44 pm    Post subject: Reply with quote

I've always wondered how unit pathing works. The only thing I've ever programmed is find the exit out of a maze. And all that needs is a simple algorithm:
1.) take a step north and record progress
2.) If fail, go east and record progress
3.) If fail, go south and record progress
4.) If fail, go west and record progress
5.) If fail, back track, recording where you have been
6.) If you end at start, and you are blocked by previous paths, it is impossible
7.) Back to 1.) until you reach end

Looks like I've got a long time until I can do stuff like A*. Oh well I guess that's what the college classes I signed up for are for Confused
Back to top
View user's profile
HunterXI



Joined: 26 Dec 2003
Posts: 476
Location: Playing like there is no tomorrow.



PostPosted: Sat Jul 31, 2004 8:33 pm    Post subject: Reply with quote

Johnh wrote:
I've always wondered how unit pathing works. The only thing I've ever programmed is find the exit out of a maze. And all that needs is a simple algorithm:
1.) take a step north and record progress
2.) If fail, go east and record progress
3.) If fail, go south and record progress
4.) If fail, go west and record progress
5.) If fail, back track, recording where you have been
6.) If you end at start, and you are blocked by previous paths, it is impossible
7.) Back to 1.) until you reach end

Looks like I've got a long time until I can do stuff like A*. Oh well I guess that's what the college classes I signed up for are for Confused


welcome to life! That's it's motto. Maybe just a "blind-grope-the-wall-until-you-get-it-right" could work? well, for fog of war, anyway.
Back to top
View user's profile
jollyreaper



Joined: 20 Jun 2003
Posts: 181



PostPosted: Tue Aug 03, 2004 12:10 am    Post subject: Reply with quote

Well, the Dune 2 solution was to essentially have no elevated terrain. That precluded the possibility of bottlenecking in places. While you can't go quite that basic in a modern game, you could be careful with the way the maps are constructed so that you don't have too devious of bottlenecks.

The biggest problem with the pathfinding is that the units simply cannot engage the enemy in a sensible fashion, they always end up trickling into range one by one and are putting their single weapon up against a great many enemy weapons.

The only two solutions for that problem I can think of are a) make a game where the player only has a few powerful units, so massing of firepower isn't as big of an issue or b) implement some sort of formation system that can take terrain features into account. The formations need not be complex, simply putting the heavy melee units out in front, the lighter ranged units in back. "Front" is determined to be whatever the direction of motion is. If there are lighter units in the game that are very important, such as TA's flimsy but vital radar jammer bots, they would automatically be placed in the center and best-defended part of the formation. Anti-air units, if any, would also go there. Protected from enemy ground units, centrally located to best cover the formation from air attack.

Regarding the graphics, I like what you're doing with them! The tanks have a sort of WWI/anime look. Different, but nice!
Back to top
View user's profile
HunterXI



Joined: 26 Dec 2003
Posts: 476
Location: Playing like there is no tomorrow.



PostPosted: Wed Sep 08, 2004 12:39 am    Post subject: Reply with quote

So, Moonpod, have you guys figures out this problem yet? Will I be amazed with the solution? Smile
Back to top
View user's profile
Gravitron



Joined: 12 Jan 2004
Posts: 125
Location: Isra(H)el



PostPosted: Tue Nov 30, 2004 6:50 pm    Post subject: Reply with quote

I believe byte pushers at westwood were institutionalized over trying to install path finding.

Any programmer who was around that block came back telling frightening stories.
In short, path finding AI is the worst and hardest thing to code (and players complain of it the most as well) and can take the better part of the development due to its complexity.

P.S.
My name is captain obvious, it's 1 AM and I was bored.
Wink
Back to top
View user's profile Visit poster's website AIM Address Yahoo Messenger
Pfhoenix



Joined: 29 Jan 2004
Posts: 2



PostPosted: Mon Dec 20, 2004 5:56 pm    Post subject: Reply with quote

An algorithm that I've had fairly decent performance and efficiency with is as follows :

1) at every step, sort the possible directions to move in by how far a step in each direction would be from the end goal
2) go in the direction that has the least cost (distance to end goal) and isn't blocked

What this algorithm lacks is any checking for "is this path that I've found the shortest or best given any movement coordination with other objects that are moving with me". If you have maps that are by and large open, or the blocking areas aren't maze-like, this method is generally fast and results in fairly quickest route paths.

You could, if you wanted to place a real burden on your map designers, go the route the Unreal Engine takes - placing nodes in key spots on the map and generate a path network (very similar in operation to networks and how routers pass packets around), weighting the cost of each path connection by the general width (maybe in unit sizes standing side by side) of a formation that could use the path unimpeded.

Largely, the biggest problem with path-finding is that there is no perfect solution; ergo, the best method is the one that fits your map topology the best and results in the movement behavior for your objects that you desire.

- Pfhoenix
Back to top
View user's profile Visit poster's website
coldsnickersbar



Joined: 10 Dec 2003
Posts: 14



PostPosted: Sat Apr 09, 2005 4:43 am    Post subject: Reply with quote

I've coded A* before, and let me just agree with this team here. It's intensive. Someone here mentioned having units look in a straight line, but the problem is: even evaluating a straight line is more complicated than you might think at first glance. Using this algorithm to evaluate a path that doesn't go into dead ends, death traps, or less efficient terrain is hell on your CPU.

However, there are a few precursors to A* that are less complex. Without writing a book on the subject, let me suggest that you can switch amongst them.

I don't know if it's any help to you at all (and maybe you already do this), but perhaps you could use a combination of many algorithms for different situations. Like the Dijkstra algorithm may end up storing more into the heap, but would also require less evaluations, and would trade CPU work for memory space. The BFS (Best First Search) could be used for situations where a unit wouldn't need to commonly evaluate complex paths. This algorithm is very simple and taxes the CPU less AND uses less memory.

Man. I've never had to combine A* with any idea of the 'Fog of War', though. In all my projects, my subject knew where every barrier was and didn't have to run blindly, then have a barrier suddenly be revealed to it and have to re-evaluate a new path around it. Also, I imagine making units chase another moving unit will tax the processor even more than that.
Back to top
View user's profile Visit poster's website Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    Discussion Pod Forum Index -> Developer Diary All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group