Jump to content

  • Log In with Google      Sign In   
  • Create Account


Scouting smartly?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
4 replies to this topic

#1 Moon Dancer   Members   -  Reputation: 103

Like
0Likes
Like

Posted 30 July 2013 - 08:21 AM

Update: thanks for all the no-reply, after some reading it seems that this is traveling salesman problem...


Edited by Moon Dancer, 31 July 2013 - 08:00 AM.


Sponsor:

#2 Moon Dancer   Members   -  Reputation: 103

Like
0Likes
Like

Posted 31 July 2013 - 05:44 AM

/Update:

wrote a simple recursive search, it's kinda fcking slow =d

        class rs_data
        {
            public List<ExplorerPoint> bestpath = null;
            public float bestpath_hdist = float.MaxValue;
        }

        private float recursive_search(float traveleddist, Vector3D lastpoint, List<ExplorerPoint> xplist, rs_data rs_data, int deep=0, List<ExplorerPoint> chain=null)
        {
            if (rs_data.bestpath_hdist < traveleddist)
                return traveleddist;
            if (chain == null)
                chain = new List<ExplorerPoint>();
            if (xplist.Count == 0)
            {
                if (traveleddist < rs_data.bestpath_hdist)
                {
                    rs_data.bestpath_hdist = traveleddist;
                    rs_data.bestpath = chain.ToList();
                    //backtrack last ?
                }
                return traveleddist;
            }
            var newlist = xplist.OrderBy(
                w => { return heuristicDistance((float)lastpoint.X, (float)lastpoint.Y, (float)w.Pos.X, (float)w.Pos.Y); });
            ExplorerPoint bestnode = null;
            float bestnode_dist = float.MaxValue;
            var i = 1;
            if (deep < 10)
                i = 2;

            foreach (var xp1 in newlist)
            {
                i--;
                if (i == -1)
                    break;
                var hdist = (float)Math.Sqrt(heuristicDistance((float)xp1.Pos.X, (float)xp1.Pos.Y, (float)lastpoint.X, (float)lastpoint.Y));
                if ((traveleddist + hdist) > rs_data.bestpath_hdist)
                    continue;

                var n = newlist.ToList();
                n.Remove(xp1);
                chain.Add(xp1);
                var res = recursive_search(traveleddist + hdist, xp1.Pos, n, rs_data, deep + 1, chain);
                chain.RemoveAt(chain.Count - 1);
                if (res < bestnode_dist)
                {
                    bestnode = xp1;
                    bestnode_dist = res;
                }
            }
            return bestnode_dist;
        }



#3 Álvaro   Crossbones+   -  Reputation: 13011

Like
0Likes
Like

Posted 31 July 2013 - 06:32 AM

Let me try to understand your problem, because it's not immediately clear from the pictures. You have a finite set of points (the red dots), you are currently at one of them and you want to design a path through all the other nodes, minimizing total distance travelled. Is that it? If so, ask Google about the "travelling salesman problem": The original problem includes returning to the starting point at the end of the path, but you can probably use pretty much the same algorithms in your case.

 

If that is not your problem, please try to state it as clearly as possible.



#4 IADaveMark   Moderators   -  Reputation: 2415

Like
0Likes
Like

Posted 08 August 2013 - 05:54 PM

Never delete your original post and say "never mind, I've solved it". It just confuses people who come in later.


Dave Mark - President and Lead Designer of Intrinsic Algorithm LLC

Professional consultant on game AI, mathematical modeling, simulation modeling
Co-advisor of the GDC AI Summit
Co-founder of the AI Game Programmers Guild
Author of the book, Behavioral Mathematics for Game AI

Blogs I write:
IA News - What's happening at IA | IA on AI - AI news and notes | Post-Play'em - Observations on AI of games I play

"Reducing the world to mathematical equations!"

#5 AngleWyrm   Members   -  Reputation: 554

Like
0Likes
Like

Posted 18 August 2013 - 04:18 PM

Also, other people might have the same or a very similar problem. So solutions can be valuable to more than one person.


Edited by AngleWyrm, 18 August 2013 - 04:19 PM.

--"I'm not at home right now, but" = lights on, but no ones home




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS