Archived

This topic is now archived and is closed to further replies.

Riddle: Nodes and Perimeters

This topic is 5045 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Riddle: there is a grid (size not important) with 10 randomly placed nodes on it. Which of the 10 nodes constitute the "perimeter"? In Context: My game is tile based map and you can place "bases" on the map. 3 or more bases on the map triangulate and create an Area of Influence which gives your units increased bonuses and such. However, for more than 3 bases, i'm not sure how to mathmatically select which ones are the perimeter. I could create a triangle of each base to each other base, but the goal is efficiency here. Example: Here are the nodes:
**********************
*     X              *
*  X                 *
*                    *
*             X     X*
*                    *
*     X              *
*                   X*
*                    *
*                    *
*                    *
*   X                *
*                    *
*             X      *
*X                   *
*                 X  *
**********************
 
By human intuition, you know that these are the {P}erimeter ones, and the others are {I}nterior nodes:
**********************
*     P              *
*  P                 *
*                    *
*             I     P*
*                    *
*     I              *
*                   P*
*                    *
*                    *
*                    *
*   I                *
*                    *
*             I      *
*P                   *
*                 P  *
**********************
 
But how did you know? I can't think if a specifically great way to figure out which are which mathmatically. Any puzzle solvers out there, please feel free to suggest a mathmatical solution. [edited by - leiavoia on February 21, 2004 6:44:21 PM]

Share this post


Link to post
Share on other sites
You may need something more advanced than simply convex hulls, depending on your game.

For example, say you put a base very far away from the rest of your bases. Your area of influence would not extend all the way out there. Sure, your outpost base would exert influence, but it would be an influence of its own, not part of the main group.

Also, what you've defined as perimeter may not necessarily be so.

Here's the example you gave:


**********************
* P *
* P *
* *
* I P*
* *
* I *
* P*
* *
* *
* *
* I *
* *
* I E *
*P *
* P *
**********************


Now, notice there is an "E" in the lower right corner. This represents an enemy base. The interior base next to the enemy base should realistically no longer be considered interior, but it too is a perimeter base.

Of course, I don't know your game, so perhaps this doesn't apply. I just wanted to point out that convex hull's may not be the complete solution to your problem.

-Blazeroni

[edited by - blazeroni on February 21, 2004 9:19:42 PM]

[edited by - blazeroni on February 21, 2004 9:20:24 PM]

Share this post


Link to post
Share on other sites
those are all very good points. Also, thanks for the link. It was very informative and forced me to go install java correctly :-)

In my game, if a unit is inside the perimeter of your bases, it gains +X in a variety of stats, multiplied by the number of bases a player has. If there is an enemy base, it does not nullify the effects of the other player, rather he gains bonuses as well. The only way around it is to A) blow up the enemy's bases, or B) have more bases in the area than the enemy does. Your area of influence can overlap everyone elses, in other words.

Now it's a TBS game, so the strategy is that when you invade enemy territory you need all the bonuses you can get in order to have the edge. Therefore, with the perimeter idea, you can theoretically flank and surround the enemy and build bases gradually behind him. Thus, you can butter him up before going in for the kill, or at least evening the odds a bit

the other idea i had was to have the bases emit a graduated sphere of influence instead of an area made by a convex hull of all bases. However, this strategy, while probably more realistic, eliminates the rather unique feel of trying to "wrap" your enemies. The game is very abstract in nature, so i'm looking for interesting gameplay more than realism (since it has no real theme anyway)

http://www.project-axis.net/

[edited by - leiavoia on February 21, 2004 9:45:26 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by leiavoia
the other idea i had was to have the bases emit a graduated sphere of influence instead of an area made by a convex hull of all bases. However, this strategy, while probably more realistic, eliminates the rather unique feel of trying to "wrap" your enemies. The game is very abstract in nature, so i''m looking for interesting gameplay more than realism (since it has no real theme anyway)

i know you didn''t really ask, but i will say it anyway... i like this way better. you could still "wrap" your enemy by placing bases around his bases, as long as your new bases'' influence sphere spreads across theirs. you could also vary the size of the influence based on the size of the base (or some other factor), and give bigger bonuses where spheres of influence overlap.

just my unasked for 2 cents...

Share this post


Link to post
Share on other sites
Here is how I would do it:

Step 1: Triangulate all of the bases


Step 2: Eliminate triangles with enemies in them
This is a simple point in triangle test. This works even if the enemy base is inside the base.


Step 3: Find the outer edges
Outer edges are not bordered by another edge (ie. an interior triangle is bordered on all three sides while).


Below is the results of all of the steps:


If the enemy base was inside of the other base:



Share this post


Link to post
Share on other sites
as it is, my way is more like this (cut from my design doc):



So the blue axis (aka "empire") here get a relative bonus of +3 while the red gets +5. You can see how they overlap. Both axes still get there respective bonuses in the "no mans land", it''s just the in that area, red has a slight advantage with +5 vs +3 (net +2), and in the lower right area (probably red''s starting region for example) red has a dominant advantage with +5 vs +0.

Now with this "rubber band" method, you could take your axis with many bases already placed on the map, sneak behind enemy lines, and build just one base and all your "influence" would snap over the enemy territory. cool!

With the spherical influence model, you can''t do that. instead, you would have to make successive penatrations into the enemy territory by building several bases in a line one after the other until you can safely get down to the core or your goal.

The rubber band model lends itself to abuse however. If i build a million bases on my edge of the map, then build one on yours, kaching! Now i ownz joo! With the spherical model, it''s a long hard slog to get influence where i want it since it does not extend influence from the bases i have far away. But they both have their merits, to be sure.

Share this post


Link to post
Share on other sites
The convex hull is a nice way to do it. To form your convex hull, you could create an edge (or 3d analogy: a plane) from each base to each other base and see if all your other bases fall on the one side of that edge. If they do, that edge is a perimeter edge.

Also as an optimization technique, once you form your first edge, you know that those bases will participate in at least one other perimiter edge so you can merely test those against the remaining bases, and repeat the process for the new edges. In this way, hopefully you can improve the efficiency of this algorithm.

Share this post


Link to post
Share on other sites