Sign in to follow this  
Aisu Uizaado

Scouting smartly?

Recommended Posts

Aisu Uizaado    103

/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;
        }

Share this post


Link to post
Share on other sites
alvaro    21263

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.

Share this post


Link to post
Share on other sites
AngleWyrm    554

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this