/agdg/ - Amateur Game Development General

>>21297

>As the video shows it takes the algorithm over 20 secs to find the path from the bottom left to the top right which is totally unacceptable

That's bullshit bro. Post your code.

>>21306

Part II:

while ds_priority_empty(dsp_Frontier) = false
{
    CombinedString = ds_priority_delete_min(dsp_Frontier)
    scr_Separate2XYZStrings(CombinedString)
    CurrentHexXYZ = var_StringXYZ1
    PrevHexXYZ = var_StringXYZ2
    scr_HexNeighborsString(CurrentHexXYZ)
    for (var Neighbor =5; Neighbor >=0; Neighbor--)
    {
        scr_SearchInArray(arr_TacticalHexCubeCoords, 0,0,var_GridHorz,var_GridVert,arr_Neighbors[Neighbor,0])
        if arr_Neighbors[Neighbor,0] != "a"
        {
            Terrain = arr_TacticalHexTerrain[var_ArrayX,var_ArrayY]
            MCost = arr_MovementCosts[Terrain]
            scr_SearchInArray(arr_Visited, 0,0,0,VisitedHexes,CurrentHexXYZ)
            PrevMCost = arr_Visited[2, var_ArrayY]
            TotalMCost = PrevMCost + MCost
            if MCost != -1 
            {
                scr_SearchInArray(arr_Visited, 0,0,0,VisitedHexes,arr_Neighbors[Neighbor,0])
                if var_ArrayY != -1
                {
                    //Old Hex already in the array
                    if TotalMCost >= arr_Visited[ 2, var_ArrayY] {/*Previous path was shorter, do nothing.*/}
                    else
                    {
                        //New path is shorter, replace old path
                        CombinedString = string(arr_Neighbors[Neighbor,0]) + "/" + string(CurrentHexXYZ)
                        Priority = TotalMCost + scr_HexCubeDistance(arr_Neighbors[Neighbor,0],GoalXYZ)
                        ds_priority_add(dsp_Frontier, CombinedString,Priority)
                        arr_Visited [2, var_ArrayY] = TotalMCost
                        arr_Visited [1, var_ArrayY] = CurrentHexXYZ
                        arr_Visited [0, var_ArrayY] = arr_Neighbors[Neighbor,0]
                    }
                }
                else 
                {
                //This is a new hex
                VisitedHexes++
                CombinedString = string(arr_Neighbors[Neighbor,0]) + "/" + string(CurrentHexXYZ)
                Priority = TotalMCost + scr_HexCubeDistance(arr_Neighbors[Neighbor,0],GoalXYZ)
                ds_priority_add(dsp_Frontier, CombinedString,Priority)
                arr_Visited [2, VisitedHexes] = TotalMCost
                arr_Visited [1, VisitedHexes] = CurrentHexXYZ
                arr_Visited [0, VisitedHexes] = arr_Neighbors[Neighbor,0]
                if arr_Neighbors[Neighbor,0] = GoalXYZ {ds_priority_clear(dsp_Frontier);break}
                }
            }
        }
    }
}

scr_SearchInArray (arr_Visited,0,0,0,VisitedHexes,GoalXYZ)
dsl_Path = ds_list_create()
ds_list_insert (dsl_Path,0,GoalXYZ)

do 
{
    CurrentHexXYZ = ds_list_find_value(dsl_Path,0)
    scr_SearchInArray(arr_Visited,0,0,0,VisitedHexes,CurrentHexXYZ)
    if var_ArrayY = -1 {show_message("No Path possible!");var_Goal = "a";break;}
    PrevHexXYZ = arr_Visited [1, var_ArrayY]
    ds_list_insert (dsl_Path,0,PrevHexXYZ)
}
until (UnitXYZ = ds_list_find_value(dsl_Path,0))
ds_list_delete(dsl_Path,0)

If you want the code of any of the scripts just tell me.

>>21306

>Oh, it's also written in gamemaker's GML.

Fug. I've never used that, so I can't really say much for sure. 20 seconds does seems excessive compared to a python implementation though. If I were to guess it would be the searchInArray calls that were slowing it down, just going by the name. Why is it called in each step/what does it do?

Also, have you tried just using a breadth first search, just to compare?

(Also, to answer the original question, have you considered precomputing paths when you generate the map? If you don't have rules like 1UPT it might work).

>>21324

I have the hexes in 2d arrays layered on top of each other to make a 3d array (as GM doesn't support them natively). What I do there is I search for the XY of the hex's coordinate in the array that saves those and then feed that into the terrain array to find out what terrain the hex has.

The SearchInArray script is pretty basic.

var_ArrayX = -1
var_ArrayY = -1
for (var Y = argument4; Y >= argument2; Y --)
{
    for (var X = argument3; X >= argument1; X --)
    {
        if argument0 [X,Y] = argument5
        {
            var_ArrayX = X
            var_ArrayY = Y;
            X = -1;
            Y = -1;
        }
    }
}

>>21327

Oh and to explain the script a little:

argument0 = the array to search in

argument1 = top-left x of the region to search in

argument2 = top-left y of the region to search in

argument3 = bottom-right x of the region to search in

argument4 =bottom-right y of the region to search in

argument5 = what is looked for in the array

>>21327

> What I do there is I search for the XY of the hex's coordinate in the array that saves those

Shouldn't they be at X, Y?

Also what is VisitedHexes for? It looks like you're storing stuff in the order you process them but I'm not sure why.

>>21339

>Shouldn't they be at X, Y?

I meant that.

>Also what is VisitedHexes for? It looks like you're storing stuff in the order you process them but I'm not sure why.

VisitedHexes is just a counter so I know the Y in the array arr_Visited I have to save new hexes to. In arr_Visited I have the hex, the hex that the algorithm came from and the movement cost up to this point.

>>21306

Does gamemaker have profiling tools?

>>21297

what are u use game engine ?

I can't say much about the posted code, since I neither have an abundance of A* knowledge, nor GML experience.

However, I have implemented pathfinding algorithms in other languages and can say that it's possible to incorrectly implement A* such that it finds a path but horribly inefficiently. One suggestion I have to you is to render the paths that your algorithm is calculating. This can help you to determine if your implementation is correctly ignoring bad choices.

Another suggestion, is to change that map generation code. Real land doesn't have scattered, densely packed lakes blocking movement so ubiquitously.

Already mentioned is the possibility to precalculate and store paths. This is a good idea if you know the pathfinding won't later be affected by terrain changes (or if you know such changes are rare enough to simply re-calculate affected paths). I wouldn't say, though that you should store a path for every tile moving to every other tile. I'd group the terrain into logical areas, then come up with some paths between those areas if this is your goal.

Finally, there are some optimizations of A* that can provide even more of a speed boost in pathfinding, such as the Jump Point Search algorithm. A google search will give you details on that. JPS specifically works best if the map has certain qualities (though I forget exactly what), and it needs a little adjustment if your terrain has varying movement costs, iirc.

>>21367

I'd look to see if you can optimize your SearchInArray function, or better yet, figure out how to get rid of it altogether. From what I see, you seem to be calling that function up to twice per hex in the search. and each time it is called, it seems to look through an array of, apparently, ever growing size.

First thanks all for helping me out here.

>>21383

I'll look at the other stuff you suggested later. It's getting late over here. But are you sure SearchInArray is the culprit here? The profile says it's using around 10% of the resources that scr_HexNeighborString or more specifically the script VariableToArrayXY called within it does. And I don't have any idea how I'd get a hex's terrain without looking it up in the corresponding array one way or another.

The "ever growing array" you mention is the array I save each hex into so I can reconstruct the path when I finally find GoalXYZ. I can't imagine how, but if I can do without it please tell me.

And map "generation" is randomly assigning each hex a terrain type when I set up the map. It's basically just so I have something to test on and in no way close to what I want to have in the end. The end goal is continents, islands and big oceans.

>>21385

Will look at when I wake up.

>>21388

Well, earlier, you said that scr_VariableToArrayXY is an older version of scr_SearchInArray, and your code above makes no mention of VariableToArrayXY, so I assume that it was simply replaced by scr_SearchInArray calls. The profile results you posted more clearly point to VariableToArrayXY as being the location where most of your pathfinding time is spent, about 44% of the application's time. The rest of your pathfinding code accounts for about 4% of the application's time. You also mentioned that you're doing some array searches because GM doesn't support 3d arrays, and I suspect that that may be related. The way you are using SearchInArray seems to be an attempt to get around the apparent lack of custom data structures in GML? I don't know, like I said, not sure what GML can and can do, since I have no experience.

A better way to get around this would, I think, be to create a Map (the data structure, not a traditional map) for every hex, containing all of the details for that hex. You'd have a key value pair for the hex's terrain, visited state, each coordinate, it's movement cost, and the current lowest cost to get to the hex in your current pathfinding search. That's only 7 items to search for per hex.

Using an array for each of those 6 or 7 values you need to track will only get continually worse as the number of hexes visited increases.

Again, I'm not familiar enough with GML, but if you can make an array of maps (or an array of pointers to the maps for each hex), that should be far more efficient. Not quite as efficient, I think, as using a more capable language, but still far better than using arrays the way you are doing.

Another recommendation is to see if there are pathfinding extensions available that will do all of this for you. I quick google search for gamemaker pathfinding showed a result of exactly that type from 2013. Not sure if it is still usable/updated, etc., but it might be worth checking out so you can avoid re-inventing the wheel (unless of course you are intrigued with this particular wheel, it's a fun wheel to figure out!).

>>21390

Adding to that, one thing I would definitely look into is how your algorithm works with no obstacles at all. It should follow two straight paths, unless the goal can be reached with just one.

>>21393

Well, I had a bit more time to take a look at things. I'm going to have to implement some sort of A* pathfinding myself sometime soon, so why the hell not, eh? Your results for a clear, uniform field aren't entirely odd, though the third one is a little more random than I was expecting. It could be that A* acts a little less consistently on a hex grid, but the odd shape of the northeast side of the searched area is... odd. The resulting path was optimal enough due to symmetry of movement.

I'm used to the terminology used on wikipedia's explanation and pseudocode, so my questions are going to use that terminology.

Why are you concerned about 3D? All I see here is a 2D hex grid. While there are technically three dimensions of movement on a hex grid, that's not at all important to implementing a search. The only thing that is important is to know what any hex's neighbors are.

You're using the variable name dsp_Frontier... is that equivalent to the open set? I think it is, but I want to be certain.

What represents the closed set? arr_Visited?

Is the use of CombinedString your way of keeping track of the parent of a hex? I'm pretty sure that's the case, but again, wanna be certain. I don't think this is causing speed problems, but I would not at all do this this way. I'd use ds_map_create to create a map to store this data. From the warnings in the GML documentation, though, it sounds like their implementation of maps is inefficient, but I bet you'd not notice that except maybe on full map crossings if you can fix the major slowdown.

In your section commented with "New path is shorter, replace old path", you don't actually replace the priority of the value, you actually are adding a new value/priority pair to the priority queue without removing the old one. Not sure if this will cause issues (in fact, I suspect it wouldn't do anything but maybe slow things down a bit), but if you ever need to squeeze every last bit of speed out of things, fixing this might help.

I still think scr_SearchInArray is your biggest problem. If anything I would suggest creating three maps (ds_map_create); one to which you add closed hexes (things that are in the closed set), one to which you add hexes that are in the open set, and one final one which would store the parent of the hexes (rather than using your combined string approach). Doing this, might just solve the last two issues, also. Again, it sounds like GM's map data structure implementation isn't quite efficient, but I'd still wager to say this would be the better way to do things. It might be worth it to see if there is a better map data structure implementation available as an extension to GM.

Finaly, one thing that bugged me, When you are testing to see if the previous path is shorter, you can instead test if the previous path is longer and get rid of that empty { } code block. I have no idea if GML will optimize that empty code block away, and I kinda doubt that it would.basically, change:

if TotalMCost >= arr_Visited[ 2, var_ArrayY] {/*Previous path was shorter, do nothing.*/}
                    else

with

if TotalMCost < arr_Visited[ 2, var_ArrayY]

>>21297

>So the question is how do I cut that down to < 0.5 secs hopefully on maps even larger than this?

>Also I guess: Pathfinding general.

This is above my pay grade, but I heard about GPU pathfinding using the parallel processing to run concurrent algorithm. Not sure how much shiny graphics need to be sacrificed for better AI responsiveness.

>>21408

>>21438

>That's because every second line is offset.

That's the hard way to do it. The easy way is to just be consistent, and make each row down be offset to the right half a hex. If you're doing wraparound, everything works out just fine with no additional considerations. If not, just do X coord modulus map width, you'll get the correct X to use no matter what. And the end result is that the neighbors are consistent, as are the directions.

>when two entries in a priority queue have the same priority Gamemaker picks the newest one.

Hmmm. If GML allows real values as the priority for your priority queue (it ought to), and if your costs will always be integers (Easy to design), then you can accumulate the costs, then add a fractional value to sort out hexes the way you want them sorted. Kinda roundabout, but if you just keep a count of the number of hexes visited, you can use that times something like 0.00001. Add or subtract it from the priority depending on the sort order needed.

>However on one of my randomly generated maps it checked basically the same amount of hexes as what I had before.

Yeah. That's pretty expected in "porous" maps. Which is the best way I can describe a fully random map like that. Which is also the reason I suggested not testing on them. lol

>Does anybody have an idea how to make the heuristic play nice with wrap around maps?

Calculate two distances along the X axis. The first is if you go east only. The second is if you go west only. Use the smallest distance. If you want the Y axis to wrap too, do the same calculation with the Y coords.

function xDistance(startX, goalX)
  if goalX > startX then
    eastDistance = goalX - startX
    westDistance = mapWidth + startX - goalX
  else
    eastDistance = mapWidth + goalX - startX
    westDistance = startX - goalX
  end
  if eastDistance > westDistance then
    return westDistance
  else
    return eastDistance
  end
end

http://www.gdcvault.com/play/1022094/JPS-Over-100x-Faster-than

>Game Maker

Oh boy. And I'm not saying that to be a programming elitist, but for large-scale pathfinding, you're going to want to seriously optimize that shit.

I can't really contribute and don't feel like reading the thread, but a depth-first search is probably your best approach. Civ V is probably a good game to copy it from since the pathfinding is pretty fast and its modern, which means documentation - you can probably find some post mortems or papers written about certain aspects of the game (I found something once about how the terrain textures were procedurally generated, for example). Also, because the map in that game is immutable (the base terrain type, anyways), pathfinding can easily be broken into graphs based on island groups.

This is a good website for pathfinding in general

http://www.redblobgames.com

If I were to implement it, my first naive approach would probably be to have each cell act as a node with an edge connecting it to other cells/nodes, with a cost associated with it. Then, it simply becomes a matter of traversing the graph efficiently and favoring low-cost nodes first (although this might fail if it runs into a "pocket" where a low cost is surrounded by high costs)

>>21622

It looked incredibly neat, but he didn't say much about handling potential obstacles like units. With A* / dijkstra you can just make the tile have infinite cost, but that wont work when you've precomputed a ton of things.

>>21589

the metric would depend on the map. if bottlenecks are common, I'd search for bottlenecks and separate areas by those bottlenecks. Another way might be to randomly choose centers around the map to use for a voronoi diagram to separate out map tiles. another possibility is to calculate the number of tiles within a distance of each tile that can be reached, then use the tiles with the highest number as the centers for voronoi diagrams. Your map generation system might help with this too.

I don't think I'd use more than two levels for this in anything Civilization-like. Lowest level would be for the actual tiles, the highest level would tell you what areas' tiles to use for the lower level pathfinding. You want the difference between pathfinding tiers to be large, so the upper level(s) can prune away unimportant areas while still allowing the A* algorithm to shine in the lower level. The effectiveness of two tiers like this would be tricky if your players ever have a chance to build high speed roads in circuitous routes that would circumvent pathfinding like this.

As for updating, I wouldn't see much need to update the higher level structure unless somehow you can completely eliminate the links between areas or greatly decrease the potential costs to move from one area to another. You'd want to be sure you don't update things so often that you lose any benefits of a high level structure, You'll probably have to test this as you go, so it would be a good idea to make this a configurable value you can update as you work on the game. One big issue with a two tier system like this will be how to calculate the heuristic cost of moving from one area to another, and how expensive it is to calculate that cost.

That expense of updating the costs of the higher tier areas can be reduced by having the areas be smaller, and by updating during player turns (since in civ type games, the game waits on the player to decide things quite a lot). Again, you'll have to play around with this to see how it works. Also, you'll have to decide how to calculate the costs. should it be the highest possible cost of a path from one to another area? The average cost over all possible combination of tiles (could get incredibly expensive to update)? The cost to go from the center-most tile of one area to the center-most tile of the next area (would ignore possibly more efficient corner paths)? All of this is stuff you'll have to play around with if you want to see if it will work for you.