Re: Problem with A*(ish) path finding

Scrogu — Thu, 06 Mar 2008 08:53:33 GMT

You can declare and pass 'struct'ures instead of classes. Structures are passed by value (unless you specify 'ref').

Re: Problem with A*(ish) path finding

Rinse — Thu, 06 Mar 2008 08:24:06 GMT

Yeh in most (all?) OO languages, objects are passed by reference.

I think you've just got to make a copy of the object. By making a copy constructor 'public Thing(Thing t)' , or implementing ICloneable and creating a Clone method. If I coded more I could be more thorough.

Re: Problem with A*(ish) path finding

Austin K — Thu, 06 Mar 2008 04:55:46 GMT

The idea light bulb is: [i ] , but without the space. Silly Live messenger icons!

Anyway, someone pointed out what the problem is with it- I didn't know that if you passed a class to a function, and change values inside this class within the function it updates the original class you passed it too... I knew PHP did that, but I didn't realise C# did.

Is there an easy way to stop this happening?

Re: Problem with A*(ish) path finding

Michael Spencer — Wed, 05 Mar 2008 22:27:38 GMT

I studied graph search algorithms in class, and I KNOW I can help you find your problem -- but the forum resists my attempts to read your code or to copy it and paste it into a text editor. There are idea light bulb icons where some code should be. Could you post your code in another format (perhaps with pre tags) or post it on a web site and link it?

Problem with passing classes to functions (A*ish path finding)

Austin K — Wed, 05 Mar 2008 17:53:53 GMT

Update is in the third post, the problem is nothing to do with A* stuff! :$

Hey,

I've created a basic program to implement the A* path finding algorithm, and am having a few problems with understanding what's actually wrong with my program. Before I start, I've done it differently so that the path isn't really the shortest path, but the one that keeps the path as close to the line between the start point and the target point as possible... it wasn't deliberate at first but I just left it in when I realised my mistake because it's fairly cool.

Anyway, my problem is this. When I call the routine to find a path the first time, it works... fine. The second time I call it, it just hangs... and I have absolutely no idea why. I've gone through my code many times trying to find something that is left behind from the first time the function is called but to no avail. Hell, I've made the entire class reset to empty before it trys to recaculate the path, but it still hangs?!?

I've a class called 'tile', and a 2 dimensional array of these to form the 'grid' in the function, or 'tiles' in the update code. These tiles can either be blocked or not blocked, and if they are then the path finder should avoid these tiles.

Any help at all would be greatly appreciated... I've never been taught any of this so I've had to figure it out!

        public Vector2[] path = new Vector2[10000];
        public int pathlength;   

  public void updatepath(Tile[,] grid, Vector2 startposition, Vector2 target)
        {
                     
        Vector2[] searchedlist = new Vector2[1000];
        int searchedlistnumber = 0;

            int currentx = (int)startposition.X;
            int currenty = (int)startposition.Y;
            searchedlistnumber = 0;
            
            pathlength = 0;
            path = new Vector2[10000];


        restart:

            grid[currentx, currenty].closed = true;

            if (currentx - 1 >= 0)
            {
                if (grid[currentx - 1, currenty].isblocked == false && grid[currentx-1, currenty].closed == false)
                {

                    float pathg = 20 * Math.Abs(startposition.X - currentx + 1) + 20 * Math.Abs(startposition.Y - currenty);

                    if (grid[currentx - 1, currenty].pathF == 0)
                    {
                        searchedlist[searchedlistnumber] = new Vector2(currentx - 1, currenty);
                        searchedlistnumber += 1;
                    }

                    if (pathg < grid[currentx - 1, currenty].pathG || grid[currentx - 1, currenty].pathG == 0)
                    {
                        grid[currentx - 1, currenty].pathG = pathg;
                        grid[currentx - 1, currenty].parenttile = new Vector2(currentx, currenty);
                    }

                    grid[currentx - 1, currenty].pathH = 20 * Math.Abs(target.X - currentx + 1) + 20 * Math.Abs(target.Y - currenty);
                    grid[currentx - 1, currenty].pathF = grid[currentx - 1, currenty].pathH + grid[currentx - 1, currenty].pathG;
                }
            }

          [does the same as above but for one box to the left, one box to the top and one to the bottom in here... pretty much the same code so I've left it out...]


#region Find Minimum F value that's on an open grid box

            float minimumpathF = 0;
            Vector2 minimumvector = Vector2.Zero;

            for (int i = 0; i < searchedlistnumber; i++)
            {
                if (grid[(int)searchedlist.X, (int)searchedlist.Y].pathF < minimumpathF || minimumpathF == 0)
                {
                    if (grid[(int)searchedlist.X, (int)searchedlist.Y].closed == false)
                    {
                        minimumpathF = grid[(int)searchedlist.X, (int)searchedlist.Y].pathF;
                        minimumvector = new Vector2(searchedlist.X, searchedlist.Y);
                    }
                }
            }
#endregion

#region Move to smallest value F slot, if that's the target square then backtrack the parents of the tiles and add them to the total path
            currentx = (int)minimumvector.X;
            currenty = (int)minimumvector.Y;

            if (currentx == target.X && currenty == target.Y)
            {
                int aa = 0;
                bool atstart = false;
                while (atstart == false)
                {
                    path[aa] = grid[currentx, currenty].parenttile;
                    currentx = (int)path[aa].X;
                    currenty = (int)path[aa].Y;
                    if (path[aa] == startposition)
                    {
                        atstart = true;
                        pathlength = aa;
                    }
                    aa += 1;
                }
            }
            else
            {
                goto restart;
            }


        }
#endregion
    }
}



        protected override void Update(GameTime gameTime)
        {
            mouseState = Mouse.GetState();

     if (mouseState.LeftButton == ButtonState.Pressed)
            {

                if (mouseState.X > 100 && mouseState.X < 700)
                {
                    if (mouseState.Y > 100 && mouseState.Y < 500)
                    {
                        int currentx = ((mouseState.X - 100) - (mouseState.X - 100) % 20) / 20;
                        int currenty = ((mouseState.Y - 100) - (mouseState.Y - 100) % 20) / 20;
                        tiles[currentx, currenty].isblocked = true;
                        [updatedrawings]

                    }
                }
            }

            if (mouseState.RightButton == ButtonState.Pressed)
            {
                person = new SearchingObject();
                person.updatepath(tiles, new Vector2(2, 10), new Vector2(28, 10));
            }
}

Game Algorithms

Re: Problem with A*(ish) path finding

Re: Problem with A*(ish) path finding

Re: Problem with A*(ish) path finding

Re: Problem with A*(ish) path finding

Problem with passing classes to functions (A*ish path finding)