Path-finding over water?

[Miznia]

Is there a good way to do this? For instance, say there's a ship in the Mediterranean which wants to go home, to say, Vietnam. No Suez. Is there an obvious way to find the way home without using a routine that investigates paths through the Black Sea, North Sea, ducking under Australia, etc?

The only thing I can think of is to create a "zoomed out" map for the AI, representing the actual map but with fewer squares, so that the AI can use it to sort of approximate first. What a pain. But I bet it would work.

I'm going to take a shortcut for the over-land path finding. You know how, in Civ2, the Germans could fight a war with the Chinese by sending Horsemen across Eurasia? I'm going to have a "supply penalty" to discourage the human from doing that, and not program the AI to even think to do that. Other than that I intend to have the AI stick to roads, or board a ship. I hope that doesn't turn out lame...


Semester's done, so I'll finally be getting to work. Spent six hours playing Civ1 today. I call it "research" and have a clear conscience.

[Mark_Everson]

Hey Miznia:

I have a generic approach for long-distance path finding written up on the Clash site's Map AI page. We did some simple demos and the idea seemed to work reasonably well.

-Mark

[Dale]

Miznia:
Thinking about this for HoE, I came up with the idea of using sea zones. It'd be crazy trying to program an AI how to get from the Med to the China Sea. I'm going to approach it this way:

- Break the map into sea zones.
- Work out which sea zones connect to each other.
- Use a pathfinding formula on the sea zones (may need about 7 hops around the world) to pull out the best way.
- Tell the AI to get to the relevant sea zone.
- Tell the AI once it gets to the relevant sea zone to get to the relevant (x,y).

[Miznia]

Mark:
Actually, a long time ago I checked out that site and ran the sample program. Pretty interesting, although I suspect it provides more functionality than I need, or plan to incorporate, for the AI. It won't be able to appreciate the importance of Panama, for instance.

Dale:
Your idea is pretty much what I was thinking of, although I see that yours is better while being easier to program. My plan was to have square "regions" (say, 6x6 tiles or something) that could include ocean and land, meaning there would be no guarantee that a boat could travel between adjacent regions.

Oddly (now that I think of it), my backup plan was to use regions, anyway, and abstract naval activities as they're done in Imperialism.


(I just figured out that you don't need Java 2 for transparency. Jeez I'm stupid. I always wondered why colors needed to |= (255<<24)... Opacity! Anyway, expect a better screen capture from me in a couple of weeks... With beaches instead of blunted tiles!)

Miznia

[Mark_Everson]

Originally posted by Miznia
Mark:
Actually, a long time ago I checked out that site and ran the sample program. Pretty interesting, although I suspect it provides more functionality than I need, or plan to incorporate, for the AI. It won't be able to appreciate the importance of Panama, for instance.

Hi Miznia, I don't understand your last sentence. I may be missing something. The importance of Panama Is determined by the method. Any land neck that is of very high path density means it is an isthmus between two large land masses. If the isthmus is adjacent to two large bodies of water (found by the regions determination) then its Important. But as you say, this approach may be overkill for you.

[Miznia]

Hmm. I think I was thinking too much. Panama is important in that it's a likely route to getting somewhere, I understand that. I was thinking that the purpose of the whole method went beyond path-finding, in also giving the AI some sense of what land is strategically important to control (bottlenecks). It's this kind of insight that I don't think my AI needs.

I can increasingly see that the method would be really handy, especially on land, which has more "obstacles" to be wary of than ocean. Dividing land into regions wouldn't help much.

I think on land I'll just have it search for any path, favoring roads, and aborting (as impossible) paths with too much non-road.


Mark, can I ask if there are Virtual Machines that you prefer or avoid, or demand of Clash users? I notice with alarm that "java" runs my programs very slowly, although partial transparency looks beautiful (I don't use it, though); "jview" runs lightning fast, dithers for partial transparency (OK with me), but substitutes SansSerif for the Serif I ask for (bad). I'm very worried about how I could distribute anything with these discrepancies.

Thanks for any info/advice...

[Mark_Everson]

Hi Miznia:

Originally posted by Miznia
Mark, can I ask if there are Virtual Machines that you prefer or avoid, or demand of Clash users? I notice with alarm that "java" runs my programs very slowly, although partial transparency looks beautiful (I don't use it, though); "jview" runs lightning fast, dithers for partial transparency (OK with me), but substitutes SansSerif for the Serif I ask for (bad). I'm very worried about how I could distribute anything with these discrepancies.

We just use the Jit that comes with the SDK 1.3.1. Its a bit slow, but Clash isn't very grapihics-heavy. You can ask Gary on our forum if you like. He knows his java very well, and might have some insights. Or you can try the java forum at gamedev.net. There should be lots of people who know their sh*t there

The Map AI thing has purposes:
1. divide the map into regions (I believe this is much more important than you think, FE see 3)
2. identify important strategic areas, as you said
3. Enable sensible long-distance path finding

I didn't stress 3 in the writeup, but I think its important to your project, or will be eventually. Because regions have been identified your pathfinding can use region borders as areas any one-mode (all-land or all-sea) path must take. With regions my pathfinding will know that to go from Beijing to Capetown land paths Must have a waypoint through Siani. That is where the Regions Africa and EurAsia meet! If you know this, the cost in time of computing the path comes down dramatically. At least that's my take on it.

The idea of No-road-no-go is going to cripple your AI IMO, unless all your scenarios start out with a good road network...

[Miznia]

You can ask Gary on our forum if you like. He knows his java very well, and might have some insights. Or you can try the java forum at gamedev.net. There should be lots of people who know their sh*t there

I'll get around to that after I try some more things. In particular, I bet the thing will run a lot faster once I get rid of all the createImage()'s I had to use to simulate transparency.

but I think its important to your project, or will be eventually. Because regions have been identified your pathfinding can use region borders as areas any one-mode (all-land or all-sea) path must take. With regions my pathfinding will know that to go from Beijing to Capetown land paths Must have a waypoint through Siani. That is where the Regions Africa and EurAsia meet! If you know this, the cost in time of computing the path comes down dramatically. At least that's my take on it.
The idea of No-road-no-go is going to cripple your AI IMO, unless all your scenarios start out with a good road network...

Well, it's more like "too-much-no-road-no-go." I actually don't want the AI to walk land units from Beijing to Capetown if there are no/few roads; I would prefer the AI to decide that the trip is impossible without a boat. The main exception that comes to mind is "exploration units." They wouldn't need path-finding to explore, but they would in order to return home, or reach new "black" areas to uncover.

But that said, I do think you may be right about no-regions crippling the AI. I'm not sure. My worry about land regions is that there are more things to consider than at sea. For instance, the shortest route by road may not be the most direct route according to region adjacency. There's also ZOC and enemy possessions to worry about, creating similar problems. ...I think I see that your path-finding method could help with the roads concern. It seems, though, like an awfully expensive calcuation to have to update whenever there's a new road!

Huh. This might be more complicated than I was thinking...

[Mark_Everson]

Hey Miznia:

Originally posted by Miznia
I'll get around to that after I try some more things. In particular, I bet the thing will run a lot faster once I get rid of all the createImage()'s I had to use to simulate transparency.

Yeah, bet that was Expensive! Good luck with it!

Please keep me posted if you think any good AI thoughts! It is a topic near and dear to my heart.

[dexter4dxm]

Originally posted by Miznia
It seems, though, like an awfully expensive calcuation to have to update whenever there's a new road!

There is a similar thing in Civ3 that many people have complained about. Whenever a piece of road is built or destroyed, the game re-evaulates all the trade routes to see who can trade with each other. Needless to say, this takes up processing power, and people with systems towards the minimum requirements really take the hit on this issue.

What you have here is a simple matter of a trade-off. You have to decide what the best way to do it in gameplay terms, compared to the best way to do it in processing time terms. In my game, I had to figure out how and when you evaluate city connections to the capitol (similar to Civ3). I decided on a system that is run once each turn for each city. Things aren't updated right away, but it doesn't hurt the gameplay very much either. I suppose there are a lot of factors that go into the decision, like how many cities you will be working with, how big your maps are, and so on.

I hate pathfinding

[Mark_Everson]

Hiya Miznia:

Could you do me a favor? A lot of people are having trouble getting Clash D6 to run. But I'm not getting back error messages... It occurred to me you'd be ideal, since if there are errors you're a java guy and will know how to get them... Also since you're outside of the project, you have none of the project-specific files that might possibly be why I don't see errors on my machine (although I don't think that's the case because I tried it on my wife's comp). If you have a spare 20 min to check it out, I'd really appreciate it (see thread here and link therein)

Thanks,

Mark


On roads changing the MapAI calculation, I don't think you can do it frequently, because as has been said its very expensive. But it would take a Very special road to change the results of where the hotspots are greatly. I think we will most likely redo the calculation when the player takes a break (more than 2 min of no activity or something)

[Miznia]

Actually

Could you do me a favor? A lot of people are having trouble getting Clash D6 to run. But I'm not getting back error messages... It occurred to me you'd be ideal, since if there are errors you're a java guy and will know how to get them...

I'm a step ahead of you. A couple days ago I got around to checking out ClashD6 (as well as Civiliza 4 and HoE's first).

I didn't do the installation quite as your webpage says to. This probably limits the helpfulness of my experience... But, after putzing around with putting the JAR in different places, I got the most success from putting it in \jdk1.2\bin, where I would then run "java -jar clashd6.jar." I get the start-up menu, then scenario selection, then player selection, and then it halts, with the console window saying a certain field didn't exist. It was from/about "javax.swing.JDesktopPane," regarding a field... "OUTLINE_something_something" I think. Clash did create two text files, "economy" and "tech," I believe, which convinces me that it got to the point of doing *something*...

There's a method list, I mean a stack trace, but I don't remember what was up. Sorry I can't be more help at the moment; I'm at a lab computer, with no internet from my home computer.

since if there are errors you're a java guy and will know how to get them

Clash is the first java program I've ever downloaded. My most astute observation is that if you use "javaw" instead of "java" you won't get an error message because it's not a console app

What you have here is a simple matter of a trade-off. You have to decide what the best way to do it in gameplay terms, compared to the best way to do it in processing time terms.

I'm sure you're right, but the factors involved are not all clear to me. A fast over-land system would use regions, but potentially trespass a lot and ignore viable road solutions. I'm not sure if this is acceptable. I'm also not sure how to make a happy marriage of regions and some brute force path-finding.

I wonder what all Civ1/2 uses for path-finding? Is it really pretty stupid? In Colonization, on the northern coast of SAmer, there's a three-square bay that the computer boats can't seem to find their way out of... God forbid I have to settle for that.

[Mark_Everson]

Hi Miznia:

Well without java 3 you ain't gonna get very far. Thanks for trying it, but to save yourself grief, don't try it further till you get 1.3 one way or the other. If you get SDK 1.3 it should work, or you could just download the JRE as in step 1 of the downloads.

And thanks for putting the reply in the Clash Forum!

"A fast over-land system would use regions, but potentially trespass a lot and ignore viable road solutions. "

I may not understand your point, but The MapAI stuff Will Use Roads. I didn't state it explicitly, but it can use any roads you care to have it use... Its just that with roads you will have to recalculate every once in a while.

[Miznia]

Geeez

Shows what a "java guy" I am; I hadn't even heard of Java 3. ...Anyway, I'll get around to downloading it... I bet this answers the question of everyone on whom the game bombs after selecting civ...

"A fast over-land system would use regions, but potentially trespass a lot and ignore viable road solutions. "
The MapAI stuff Will Use Roads.

I know that, I was saying this more to Dexter, on the subject of trade-offs.

A better question for you, is how you are creating/using regions in conjunction with the path-evaluation method you have on the webpage. I think we may not mean the same thing by "regions." I'm envisioning the map chopped up into chunks that only the AI can see. The way I see it, this division is a short-cut, in being faster but stupider than a brute-force search.

Maybe I've over-simplified the issue...?

[Mark_Everson]

Re: Geeez

Originally posted by Miznia
A better question for you, is how you are creating/using regions in conjunction with the path-evaluation method you have on the webpage. I think we may not mean the same thing by "regions." I'm envisioning the map chopped up into chunks that only the AI can see. The way I see it, this division is a short-cut, in being faster but stupider than a brute-force search.

Maybe I've over-simplified the issue...?

Well first, we're not using it for anything yet. That's about a Demo 9 thing. You may be right. I think there are clever ways to use the regions info. One is that necks and hotspots are Strategically important. Just individual pathfinding by units doesn't tell you that. I bet there are probably other things, but frankly I can't think of 'em now! Too sleepy