[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 483: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/bbcode.php on line 112: preg_replace(): The /e modifier is no longer supported, use preg_replace_callback instead
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4586: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4588: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4589: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
[phpBB Debug] PHP Warning: in file /includes/functions.php on line 4590: Cannot modify header information - headers already sent by (output started at /includes/functions.php:3765)
AI Challenge Forums • View topic - Create a supply route, PathFinding.

It is currently Mon Apr 23, 2018 2:09 am Advanced search

Create a supply route, PathFinding.

Share and discuss ideas for your entries here.

Create a supply route, PathFinding.

Postby temp_dummy » Thu Oct 07, 2010 11:04 pm

temp_dummy
Colonel
 
Posts: 87
Joined: Sat Sep 11, 2010 6:00 pm

Re: Create a supply route, PathFinding.

Postby mogron » Tue Oct 12, 2010 9:31 am

Thanks! I used this idea for my newest bot. I took dist*sqrt(dist) as cost function, which works good so far.
mogron
Lieutenant
 
Posts: 18
Joined: Mon Sep 20, 2010 9:07 am

Re: Create a supply route, PathFinding.

Postby mleise » Wed Oct 13, 2010 10:32 am

So that would be "dist ^ 1.5" as mathematicans like it short - at least my teachers :geek: . The function could benefit from information on how safe the planet formation is from which the ships are departing. Say if the enemy could attack a planet in the area and win in 7 rounds it is better to keep the routes short so you can respond within 7 rounds, but still keep moving and don't sit there in a locked down defense position if possible. I haven't tried that, but it could create a local "head" planet that serves two purposes: 1. secure the other planets in the are, 2. have these ships already a little closer to the enemy or your "head" planet.
On the other hand, imagine the game is evolving around a center planet with all other planets far in the back. Depending on the ship difference between you and the enemy you may be able to send your ships all the way from the back to the front or at least jump to a planet half-way to the middle safely.
mleise
Lieutenant-Colonel
 
Posts: 42
Joined: Mon Sep 27, 2010 6:18 pm

Re: Create a supply route, PathFinding.

Postby bentie » Sat Oct 16, 2010 2:20 am

Pahtfinding might not be the best option here, perhaps something more like this:

supply.png
supply.png (21.06 KiB) Viewed 3933 times


Create a bounds of acceptable distance to deviate from the shortest path and determine which planets fall within it (breaking it down into two triangles would be helpful). Arrange the planets into a list according to there distance to the start-planet then pick say 4 or 5 of them.

I do agree that supply routes are essential, although which planet do you send them to? I'm still in the process of creating my first bot and what I am doing is finding the "center of growth rate" for the enemy and using my planet closest to that as a staging point. Will that work?
bentie
Cadet
 
Posts: 1
Joined: Fri Oct 15, 2010 12:00 pm

Re: Create a supply route, PathFinding.

Postby mogron » Sat Oct 16, 2010 9:04 am

Hi bentie,

first: I do not know if pathfinding is optimal for this, but it definitely works good. My last bot using this was in the Top40's until I resubmitted yesterday.

I'm always sending supply ships towards the nearest frontier planet. For deciding what planets are frontier planets, I started with the following:
A planet p is a frontier planet, if and only if: p is mine, and there exists an enemy planet e such that p minimizes the distance from my planets to e. In other words, p is closer to some enemy planet than all my other planets.

This method works ok, but it's not very good. For example, if two of my planets are on opposing sides of one enemy planet, only the one that is closer will be a frontier planet. My new method is similar, but allows for several planet to front one enemy planet.

Another way I've read about uses the average distance to enemy planets and own planets (see Mistmanovs' thread in this subforum).
mogron
Lieutenant
 
Posts: 18
Joined: Mon Sep 20, 2010 9:07 am

Re: Create a supply route, PathFinding.

Postby Mistmanov » Sat Oct 16, 2010 9:35 am

Attachments
supply.GIF
supply.GIF (3.97 KiB) Viewed 3890 times
Mistmanov
Colonel
 
Posts: 70
Joined: Fri Sep 24, 2010 6:50 pm

Re: Create a supply route, PathFinding.

Postby iouri_ » Sat Oct 16, 2010 12:21 pm

iouri_
Brigadier-General
 
Posts: 105
Joined: Thu Feb 11, 2010 4:16 pm
Location: Toronto, Canada

Re: Create a supply route, PathFinding.

Postby Demerzel » Sat Oct 16, 2010 7:01 pm

A* sounds nice but it's overkill - there are way too many variables that it doesn't know, and if you try to supply them you'll compound the efficiency overhead issue

setting up hops is quite simple, i went way too deep with it at first too -- pseudocode

hop(a, b)

for ( 0 -> maxDeviation)
for (planet c = 0 -> planetCount)
if (dist(a,c) + dist(b,c) <= (dist(a,b) + maxDeviation)) return c

qualify planets during or afterwards for yours or have a system setup somewhere for it to check -- and you're done
Demerzel
Colonel
 
Posts: 72
Joined: Sat Oct 02, 2010 6:06 am
Location: themendios at gee mail

Re: Create a supply route, PathFinding.

Postby Innominate » Sun Oct 17, 2010 3:14 am

My "frontier" metric is quite simple: find the minimum distance from a planet to one of mine, and to one of the enemy's. Subtract, and you get what I call the "safety". A positive safety means a planet is in your "territory", while a negative safety means it is in the enemy's territory. Then use Dijkstra's algorithm instead of A* and stop whenever you reach a planet with your minimum safety. If you only have one such planet you can use A*.

I've actually been wondering how A* is used when you have multiple possible endpoints. Do you just use a minimum of the heuristics for each destination as the composite heuristic? It seems like that would produce an admissible heuristic if your original heuristic was admissible. If you can use A* effectively with multiple endpoints, you don't have to use Dijkstra's.
Innominate
Captain
 
Posts: 22
Joined: Wed Oct 06, 2010 3:20 am

Re: Create a supply route, PathFinding.

Postby fglider » Sun Oct 17, 2010 7:01 pm

Consider looking at things not from standard top down graf analysis algorithms, but rather from starsh(i/ee)p commander at the planet X with limited fuel and natural tendency to be stuck in spaceports with spaceport women.. whatever. Still he has orders to go to battle, so check your nearest systems, which of them closer to enemy, go there. Then rinse, repeat and when you have no options you are there and ready to die :( . But remember, that your fuel is limited, so this will naturally remove any problems with single gravity point or nearest frontal planet.
fglider
Cadet
 
Posts: 5
Joined: Thu Oct 14, 2010 8:06 pm

Next

Return to Strategy

Who is online

Users browsing this forum: No registered users and 0 guests

cron