Reading maps from .map files
 

How can I define an "area" using only the .map file?

I have thought of something like this:

1. Choose a province.
2. Choose one of its neightbours.
3. Choose a province that is next to two provinces that were chosen before it. Skip over provinces already chosen. Abort if no suitable province is found.
4. Repeat 3 until you have X provinces, generally 5-8 is enough.

Take the one with most inter-connections inside the area. This is the capital of the area. It will get suitable poptype (e.g. barbarians) and map-added defenders (barbarians, tribal warriors, few horse brother commanders, Barbarian Lord with randomequip 3...). The other provinces of the area have poptypes that suite the "theme" of the area, e.g. Tribal Warriors, Tribal Cavalry, Horse Brothers & Horse's Vale, Barbarians with normal defenders), possibly with some special commanders (Barbarian Chief with randomequip 1) added in for fun.

Could a Java program working among these lines work? Any suggestions for better-working definitions of "the area", that could be a kingdom, a tribal nation, something along those lines.
Is there any easy way to discover "areas" with the same terrain type, e.g. 5 Wastes next to each other, or 8 mainly Forest and/or Mountain provinces?

Would it unbalance the game to have "areas" with similar defender types, where someone would start near barbarians/tribals inhabiting waste/plains and someone else near HI&X-bow, Knights&Longbow (only capital) etc. on plains/farmlands? Would this possibly screw someone over, while giving another easy start?

If you could add more provinces, area types, special things etc. with "script language" that would be map editing commands with few additions, would you do that? How many special provinces, area types, special things etc. would there have to be for a "random map" to be interesting?
The additions would be fairly simple, adding '#if Nbr' (Nbr is possibility of few following map commands, in %) and commands for choosing different defender types for poptypes. Like: Militia and Light Infantry with Javelins from 1-15, some Shortbows and some Heavy Infantry from 10-25, then a Knight commander with few longbows and more bows & HI with 2:1 relation from that point on.

I wonder what Gandalf, High Priest of the Random Map Cult, will say about this post... http://forum.shrapnelgames.com/images/smilies/happy.gif
Don't have your hopes too high. This is just an idea, and I might be able to get it to work, but I won't start it for a week, atleast. I have three exams left, and will start playing Morrowind after that. And I'm going to Germany in a Month. And then there is always school and life and little things like that. http://forum.shrapnelgames.com/images/smilies/wink.gif

Re: Reading maps from .map files
 

Any programming language could probably do it. Afraid I cant help you with the Java thing, I do mine in Basic.

I think you would be working with an array. Read in all of the #neighbor lines as a starting point.

The problem with "areas" is the same problem that we had with DomMap working with terrain. If an area is too large then you have people landing somewhere on the map which might be fantastic all around them, or horrible all around them. Of course some of that is going to happen but you might want to make sure that its not TOO far for a player to reach for something else.

Re: Reading maps from .map files
 

Your algorithm looks reasonable, but sometimes it will fail. Consider a small map with a chokepoint that splits map in 2. If you need to allocate 2 somewhat equal areas your algorithm will fail is the first province will be at the chokepoint. You can also fail on step 3 before finding 5-8 provinces. I think your algorithm will work well on open wraparound maps with few impasses, but not on highly segmented maps.

Generally, this kind of tasks is considered in graph theory. I would suggest some modification to your algorithm:
- the first step is to build a graph. Initially you have connected graph (at least usually)
- find simple chokepoints (nodes, which if removed would make the graph unconnected). This is easy to do by iterating through all nodes and checking if the graph is still connected or not if all incoming edges to this node are removed.
- or optionally find complex chokepoints (pair of nodes, which if removed would make the graph disconnected). This is similar to the previous step.
- Now consider graphs produced by removal of chokepoints. Each of those graphs is a "mega-area". Those are suitable for area placement. Count number of provinces in each mega-area (number of nodes) and see if there's a reasonable way to divide them in required number of area. There's no need for exact match, because some of the areas can overflow through chokepoints. This step may fail. For example, if you have 2 equal areas connected through the chokepoint, you can't make 3 "equal" areas. So you have to decide something. (see more in the following step).
- Now you have number of areas to create out of each "mega-area". Start from the most densely populated "mega-area"
(one that have least provinces per required area). Start from the most remote point from any of chokepoints. Use your original algorithm, but in step 2,3 give more preference to the province further from the chokepoint. Degree of preference should depend on density of "mega-area" population. More densely it is populated, the more preference you should give to the outward provinces.
This will let the last area overflow through the chokepoint, if necessary.
- Update the graphs to take into account possible overflow, and repeat previous step for the next densest "mega-area".

If you have larger map and fewer required areas, you may want to execute this algorithm for the size of the area approaching to total of "mega-area" areas divided by number of required areas, and after it is complete, remove outward provinces from each of the areas to reach your original target size.

Concerning implementation, I don't see any problems implementing it in Java, but this algorithm may be resource intensive (I have no idea actually), so it may be better to do it in C++. Besides you'll probably have easier time finding libraries to use (like for graph handling).

Re: Reading maps from .map files
 

programming language
At first -considering the fact that you ask if something like your pseudocode could be implemented in Java- let me say, that if you start learning Java now it will be quite a long time before you actually can do what you want. Are you thinking about taking Java courses at University? That would make time less of an factor as far a learning is concerned, but they're not known for starting with the "practical side" of things.

I would wholeheartedly suggest using (and learning) a scripting language - Ruby, Pearl, Tcl. Those are freely available, have bindings to GUI-Toolkits (like TK) which make building a graphical interface a matter of tens of lines of code and are usuable cross-plattform. What is a thing to consider as DOM is, too. And the scripts can be "wrapped" into standalone .EXEs which you can distribute.

I don't think they would pose too much of a performance problem in the time of 3 Ghz processors.

If you're interested in details, PM me. I could supply you with links etc. to a good bunch of free ressources on the net, trainers and manuals included.

algorithm
As alexti already pointed out, there are some "flaws" in your algorithm. His, on the other hand, looks overly complex to me. Something I would expect from a C++ programmer http://forum.shrapnelgames.com/images/smilies/wink.gif Think he overlooked the fact that some -how do you call it?- "boundary conditions"? are already know at start:
E.g. you could can the map file for all provinces which have only 1 or 2 neighbours - those are the choke points. A "capital" must have at least 3, better 4 land neighbours, so if the number of desired "capitals" is known, you can simply compare it ot the number of "4"s and if those are sufficient, I think you needn't do much more besides checking for duplicates among the neighbours.
Don't have the time to go into further detail now, will look into it later...

Re: Reading maps from .map files
 

I suspect that this is kind of problem where it is easier to find some available bike with round wheels rather than invent your own with rectangular ones http://forum.shrapnelgames.com/images/smilies/wink.gif If you take something like Goblin, probably you'd get most of the code you need. You can also look at http://www.kurnikov.org/links/math_links.htm in the Graph Theory section. Or just google http://forum.shrapnelgames.com/images/smilies/happy.gif

Re: Reading maps from .map files
 

Alexti, I think you're missing the point. Someone who is an experienced programmer, maybe software engineer or with an degree in computer science or something, will have little trouble understanding what those libraries do, and how to use them.

Then think of a novice:
He still has to learn the basic syntax of the language.
He can barely do a command line programm, I/O will be a major obstacle.
The concept of OO-programming (C++, Java) is new to him, integrating pre-made libraries into his programm is quite a task for him.
He'll have to delve into the mathematical background of solving problems using computer algorithms, and that of the suggested theorems in particular.

So, it seems to me, you suppose someone should learn how to operate a particle accelerator to poke a hole into a sheet of paper. May work, but won't be the most effective way unless he's going for a degree or two in atomic physics anyway http://forum.shrapnelgames.com/images/smilies/wink.gif

And we're talking about a real thin sheet of paper: 100-300 provinces (nodes) at best, with less than 750 interconnects.
A short script will really do. If you're fancy, you may implement a graph algorithm in that script language, too (haven't checked if it's already available, but it might be)

Re: Reading maps from .map files
 

That "Could a Java program using this work" line: it was originally "Would this (algorithm) work". I changed the line to make clear I'm going to make a program utilizing this, not change maps by hand, and managed to translate it to Gibberish. Confusing language, that.

I have already made a working program, ModConverter, which has a GUI and can handles Dominions's mod (text) files. However, I don't have much programming experience besides that and school stuff, and while ModConverter works without crashes it has some annoying input/output bugs, and I'm not going to reuse much code from it. So it seems I didn't plan/implement it properly.


I'm not sure if I understand that "graph" stuff, but hopefully it is just a term I don't know in English. I'll check that.
Okay, I have heard of that. I have to ask my Math teacher a few things, but I think it's doable.

Re: Reading maps from .map files
 

Doing a fast scan through the ressources, this is what I found what may be a good starting point:
http://www.cs.sunysb.edu/~algorith/info/view.html
In the 7th line, there's something called "edge-vertex-connectivity" what resembles our problem to some extent.
http://www.cs.sunysb.edu/~algorith/f...ectivity.shtml

Re: Reading maps from .map files
 

You can get some basic info at MathWorld: http://mathworld.wolfram.com/Graph.html But if you aren't familiar with graphs at all, you may be for a hard time. Either you implement your own algorithm (like the one you originally suggested) which will work on one maps, but not on others (and ti will keep you puzzled why it didn't work on a particular map). Or you have to go through some learning to find existing algorithm you could use. Your problem is more of a mathematical problem than a programming one. There isn't much to program there if you've figured out the right algorithm. But you can be proud of finding yet another interesting Dominions-related problem http://forum.shrapnelgames.com/images/smilies/wink.gif Good luck!

Re: Reading maps from .map files
 

Guys,

Mike Milchior has done a program similar to that one for another program. You can find a link to it at this site:

http://www.slooflirpa.com

Re: Reading maps from .map files
 

He isn't exactly a novice. Didn't he wrote some tools for Dom2? Anyway, if the primary idea is to learn some basics of the language and not to solve the problem of finding the "areas", it doesn't matter which algorithm to use.

I think that concept of OO-programming can be new only to old-school programmers http://forum.shrapnelgames.com/images/smilies/wink.gif Meaning that C++ (and Java, to some extent) concepts match modelling languages almost exactly, so the step of converting the model into procedures is effectively removed.

I wouldn't be so optimistic. For example, check http://domino.research.ibm.com/Comm/...arch2005.html. Just 6x6x6 cube with 2 possible values in a cell and its way beyond the computing power of modern computers.

Getting back to our particular task, the simple algorithm that would check for chokepoints would apparently have to verify if the graph is connected for each single and pair of nodes, which for province with N=200 nodes gives you about O(N^2)=40000 verifications for graph connectivity. And checking graph connectivity is not particularly fast operation. It may or may not be a problem, it's kind of estimation, where you can't say for sure without actual test. So to avoid frustration of discovering that your nicely written program can't handle large maps in reasonable time it may be better to look up for more efficient solutions from the start.

Of course, all this doesn't matter if the primary goal is to learn programming.

Re: Reading maps from .map files
 

Actually I would figure that validating whether a graph is connected or not would be an O(n) operation since you simply walk the graph from any randomly selected node and if the number of nodes in the walk is equal to the number of nodes in the graph then it is connected.

So the whole operation you described would be O(n^3).

Re: Reading maps from .map files
 

Imagine graph:
<font class="small">Code:</font><hr /><pre>
x-x-x-x-x-x-x-x-x-x
</pre><hr />
If you start your walk from any node in the middle you'll reach dead-end without passing through all the nodes, even though the graph is connected. So you need to retrace your steps to walk through all graph. I think that establishing if the graph is connected or not is O(m), where m is number of edges (neighbour connections). However it is somewhat bigger O, in sense that each operation is more costly than iterating through the node. We start from random node, mark is as "visited", select any edge outgoing from "visited" node and mark it as "travelled", mark the node it leads to as "visited" and repeat procedure selecting the next "non-travelled" edge outgoing from "visited" node. If all nodes are "visited" at the end, the graph is connected. In this method we need no more that number of edges iterations, but the most efficient implementation of it will probably involve 2 copy of list of edges and list of nodes and moving elements from one to another, which is more costly than just iterations.

Re: Reading maps from .map files
 

When you walk the graph you simply do a BFS on the graph and then color each node as you visit it and never revisit a node which is colored.

One easy method of programming this is to take a random node and push all of it's neighbors onto a stack. Then for each element on the stack check to see if the node is colored if so then ignore if not then push all of it's neighbors on the stack, bump the global count and color the node. Repeat. If at the end the global count is equal to the number of nodes in the graph then it is fully connected. A decent interview question.

The order of this is O(m) ( where m is the number of edges ). When I said the order was O(n^3) I was assuming that n~m this may not be a valid assumption. Clearly in a fully connected graph m = n^2. But most maps in dominions do not match that profile.

PS: I used the word "walk" in my 1st post which was incorrect. I should have defined what I meant which I did in this post sorry about being unclear.

Re: Reading maps from .map files
 

Yeah, it makes sense. I was thinking more, probably my original chokepoint finding approach is bad. On most real Dom2 maps, chokepoints are not of 1st or 2nd order, but 3rd or 4th or higher, which means that they are much harder to calculate. Besides huge extra drain on performance, for chokepoints with higher order a lot of various "mega-area" splits will start to appear and it is unclear how to pick "right" ones.

Thus I came up with yet another rectangular wheel (oops, I meant "mega-area" finding algorithm http://forum.shrapnelgames.com/images/smilies/wink.gif )

For each node we can introduce a sequence of metrics, 1st metric equal to number of provinces that can be reached in no more than 1 hop, 2nd metric equal to number of provinces that can be reached in no more than 2 hop etc. In practice, we will choose only one of those metrics (depending on the map size, probably). Let's say it will be 7-metric. For this metric there's an area around the node which can be reached within 7 hops. Then we can find the "core" of the mega-areas by the following procedure:
- introduce function f() for pair of the nodes, equal to the number of diffirent provinces they have in their areas.
- find where minimum of f() is loosely reached (for example where f() is different from the exact minimum by no more than 2). Those nodes are considered to be in the "cores". Obviously, nodes that are connected with each other by path that stays within "core" nodes.
- Now we can grow "mega-areas" from the cores by incrementing the range by 1. At some point "mega-areas" will start to clash, those equally remote nodes can be marked as "neutral").
- After every attempt to "grow" leads to clash, the procedure is completed. Now we can review "mega areas" and assign neutral nodes to the "mega areas" in a way to make the density of "mega-areas" most uniform.

Re: Reading maps from .map files
 

Whoa. I would need to see the results in a visualizer to see if it makes sense. That is a wacked algorithim!