Jump to content


Photo

A* Pathfinding Extension -- C++ and fast (now with GML version as well)


  • Please log in to reply
168 replies to this topic

#1 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 09 February 2013 - 06:20 AM

A* PATHFINDING EXTENSION

 

Hello everyone! I made an A* pathfinding .dll in C++ and put it into an extension.

You can use this freely without credit, even in commercial applications. However, I would greatly appreciate credit and you posting here if you found it useful.

 

______________________________________________________________________________________

EDIT:

Someone requested a GML only version of this. It will probably be a decent amount slower. However, it lets you use the features of this pathfinding on platforms other than windows.

Check the downloads for the .zip containing the .gmk. You'd need to add the AStarPathfinding folders under Scripts and Objects into your own game, but other than that it should use the same syntax as the C++ extension.

If it causes too much lag when pathing it could be modified to compute the path over multiple frames rather than all at once -- if you can't figure out how to do it and you want to then let me know.

Neither of the influence map functions are currently implemented in the GML only version.

 

Also, I found a bug (only in the C++ version now) where if you try to create a path with unitwidth > 1 it can crash when it tries to path near the bottom or right edges of the map. As long as the edges of the map are impassible and you don't explicity try to path the top left of the object to a place too close to the edge where it wouldn't fit (there is no reason to do this anyway) then it should be fine. If this is a big deal to anyone I can upload a fixed version.
______________________________________________________________________________________

DOWNLOAD:
astar.gex
astar example.gm81
astar example.exe

astar GML ONLY VERSION.zip

FEATURES: (vs. mp_grid)
Fast, especially for paths with few obstacles, even on huge maps. Uses arrays to mark open/closed tiles to avoid searching; uses binary heap to keep track of lowest cost.
Terrain can be given different costs (eg. you move slower in a forest than on a road).
Objects can be 2x2, 3x3, etc. tiles in size. Passages that allow a 1x1 object to pass through may not let larger objects pass through.

FUNCTIONS:

as_map_create(width,height,value);
// Returns a new grid to do pathfinding on with width * height squares. All squares are initialized with value (cost to move into it, negative for unwalkable).
// It's important to make open ground a value of 1 in most situations. Having values between 0 and 1 will produce paths that aren't necessarily the best paths.
// Values larger than 1 will cause the pathfinding to be slower.

as_map_destroy(map);
// Frees memory used by map.

as_map_getcell(map,x,y);
// Returns the cost of tile with given x and y (negative number for impassible).

as_map_setcell(map,x,y,value);
// Sets the cost of tile with given x and y to value (negative number for impassible).

as_map_setrectangle(map,x,y,width,height,value);
// Sets the cost of tiles in rectangle with given x, y, width, and height to given value (negative number for impassible).

as_path_create(map,xstart,ystart,xgoal,ygoal,unitwidth,diag,maxdepth);
// Returns a new path from xstart and ystart to xgoal and ygoal (the pathfinding is done when you call this function).
// The path will have length of 0 if no path can be found.
// unitwidth says how many tiles an object takes up (all objects are square, so an object with width 3 takes up 9 tiles in a square).
// The x and y values refer to the top left tile of this object.
// maxdepth is number of items in open list that will be examined before quitting and saying path can't be found.
// Set negative to make this infinite (will always find a path if availble, but may take too long on huge maps).
// if diag is 0 then the path will have no diagonal moves. If diag is 1 then diagonals will be allowed even if they cut corners.
// If diag is 2 then diagonals will be allowed only if they don't cut corners.
// This means that it is valid to move from A to B in the given picture (with X as wall) only if diag is 1:
// AX
// XB
// mp_grid doesn't allow the cutting of corners.

as_path_destroy(path);
// Frees memory used by path.

as_path_nodex(path,index);
// Returns x position of node that has given index in given path (0 is first, as_path_length-1 is last).

as_path_nodey(path,index);
// Returns y position of node that has given index in given path (0 is first, as_path_length-1 is last).

as_path_length(path);
// Returns number of nodes in path.

as_path_removefirst(path);
// Removes first node from a path (second item in path is now first and at index 0). Make sure path has a node.

as_inf_create(map,x,y,width,height,group,value);
// Creates an influence map. Adds value to all walkable tiles in map in rectangle given by x, y, width, and height.
// This provides an easy way to temporarily modify the cost of tiles on the map (eg. to avoid other moving objects or an ambush).
// If value is negative it won't be subtracted... all tiles will be marked temporarily as unwalkable.
// Is given an integer to denote its group to allow easy removal of all influence maps in the same group (don't use -1, see below).

as_inf_destroygroup(map,group);
// Destroys and frees memory used by all influence maps that have the given group (-1 to destroy all groups).
// Reverses operation done by influence map (subtracts values, makes tiles that were walkable and then turned unwalkable walkable again).
// BE CAREFUL: If you add a value with an infmap, then make the tile unwalkable with another infmap, and then delete the first infmap the operation won't be reverted.

SPEED COMPARISON:
All times measured using the high resolution timer extension, and are obviously based on the power of my computer. What is more important is the comparison to mp_grid, game maker's built in A* pathfinding. A larger and more thorough test likely should be done.
Computing a very simple path, such as a few tiles in a straight line with no obstacles takes ~0.03 milliseconds compared to ~1.2 milliseconds by mp_grid.
Computing a long path (1000 squares in a 1000 by 1000 map) with no obstacles takes ~1.4 milliseconds compared to ~250 milliseconds.
Computing a moderate path with obstacles ~0.3 milliseconds compared to ~1.2 milliseconds.
Computing a winding path that requires a lot of backtracking in general direction of start is slower: ~6 milliseconds compared to ~3 milliseconds.

If you need any help, don't be afraid to ask!


Edited by Jake Armstrong, 31 August 2015 - 09:22 PM.

  • 8

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#2 Katipo007

Katipo007

    42

  • GMC Member
  • 436 posts
  • Version:GM:Studio

Posted 09 February 2013 - 09:20 AM

so trying these when I get to my computer!
  • 0

"let your light shine before others, that they may see your good deeds and glorify your Father in heaven." - Matthew 5:16

I do not need to fear anything; for if the God of all, who created and cares for everything is for me, who or what can be against me.


#3 seZereth

seZereth

    GMC Member

  • GMC Member
  • 35 posts
  • Version:GM8

Posted 14 February 2013 - 07:49 PM

first trials seem promissing, can handle a lot of small (width 1) objects simultaneously.
love it, simple to use and very powerful!

Thanks so much!
  • 1

duellanesLogo.png

Duel-Lanes: a new way of action packed Hotseat Real Time Strategy gaming.


#4 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 16 February 2013 - 08:18 PM

Adding explanation of why you should make open ground tiles 1, and what would happen if you used less than 1 based on a PM I got:

Q (paraphrased):
Can I have tiles less than 1 if I want them to be preferred above open ground or should I just make open ground a higher number?

A:
It's a tradeoff between performance and accuracy. If you want to make absolutely sure that they always take the absolute shortest path then you have to make your preferable tiles (eg. roads) 1, which will make open tiles higher and thus everything slower. If your map isn't that big, then that might not matter. The worst that can happen is that it checks the entire map, which will already happen if you try to path to somewhere that is impossible to get to (other than directly onto a wall -- it's smart enough to realize that's impossible lol).

However, even if your roads are less than one then it will still work, your units just might not take the shortest path. Usually if they are less than one then your units will generally walk in a straighter line toward the goal across open terrain rather than backtracking to get to a road and taking that even if that would be technically faster. In the worst case, your units will ignore the roads all together, but it won't break your units still walking across open ground correctly. Your units will still usually prefer roads if they are on the way.
  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#5 Bleed

Bleed

    Chevalier

  • GMC Member
  • 763 posts
  • Version:GM:Studio

Posted 06 March 2013 - 08:21 PM

wow, seems like forever i've been waiting for something like this, it looks very promising...and it was made in c++? even more impressive.
Just one suggestion though, please, please please add isometric grid support? i would forever worship you.

The sadly no longer supported A* by HomebrewPC was pretty fast also and it was based on Delphi code, but that too lacked iso support Posted Image, although it could theoretically work with those grid types.

Thank you for making this, i will continue to track this topic.
  • 0

rlztjp_zpsoqffaixe.jpg


#6 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 06 March 2013 - 11:46 PM

Thanks so much!

I'm open to adding isometric grid support, but I'm not entirely sure what isometric grid support would be. If I was making an isometric game I would still have the game coordinates be in a traditional x, y grid and then just convert those positions to x, y screen coordinates based on the position of the fake isometric camera. For example the pathfinding/game grid would look something like:

Posted Image

and then, before drawing (like in end step or something), the positions could be calculated (where xpos, ypos are grid coordinates):

x = (xpos + ypos)/2 * cellsize;
y = (xpos - ypos)/2 * cellsize;
depth = -y;

  • 1

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#7 Bleed

Bleed

    Chevalier

  • GMC Member
  • 763 posts
  • Version:GM:Studio

Posted 07 March 2013 - 04:06 PM

Would have to test that out when i get the time, even though it will mean having to rewrite my current project from scratch.
Anyway i have some questions :

- When you say it will work without problems on huge maps, how huge to be exact?...will it work ok for example on a 50000 x 50000 and 32 x 32 cell map?
- What is it using to remove obsolete array entries? does those get removed too when using as_map_destroy?
- What techniqueshould we use when dealing with huge maps, it it ok to make the grid size equal to the room dimensions, even if its humungous, or should we split it into smaller parts?


I guess what i'm asking is, what are the extensions limits?


By the way, you are now one of my favorite persons on gmc, kudos to you sir, i'm just hoping you will not abandon and continue to improve this extension.
  • 0

rlztjp_zpsoqffaixe.jpg


#8 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 07 March 2013 - 11:46 PM

Thanks again!!

This pathfinding extension differs from mp_grid in that there is no concept of pixels or cell size. When you create the map, its width should be [map width in pixels] divided by [cell width in pixels], etc. That's why in the example (where the cells are all 16x16 pixels) creating a path is done with:

as_path_create(obj_map.map,x div 16, y div 16, mouse_x div 16, mouse_y div 16, width, 2, -1);

x div 16 returns 0 for x 0-15, 1 for x 16-31, etc.

Then when getting the coordinates to go to we multiply the grid coordinate by the cell size:
gox = as_path_nodex(path,0)*16;
goy = as_path_nodey(path,0)*16;
// to get center of cell instead of top left, add 16/2 = 8 to gox and goy

To make it work for 32x32 cells, simply change all occurrences of 16 to 32. I probably should have used a cellsize variable in the example instead of hardcoding in 16, but oh well :)

If you wanted to use the pathfinding in an isometric game without changing anything else, you can do similar conversions (it will depend on the game layout to configure it exactly right, but something like):

as_path_create(obj_map.map, floor((x / 32) + (y / 32)), floor((x / 32) - (y / 32)), floor((mouse_x / 32) + (mouse_y / 32)), floor((mouse_x/ 32) - (mouse_y / 32)), width, 2, -1);

gox = (as_path_nodex(path,0) + as_path_nodey(path,0))/2 * 32;
goy = (as_path_nodex(path,0) - as_path_nodey(path,0))/2 * 32;

There is "theoretically" no hard limit to the extension. In practice, 50000x50000 CELLS is absolutely ridiculous, but 50000x50000 pixels of 32x32 cells (about 1563x1563 cells) would be doable (my tests were with 1000 x 1000). I use loops and not recursion so there shouldn't be any stack overflows. In terms of memory the biggest use of RAM will be the map:
The map stores a double and two ints for each cell (8 + 4 + 4 = 16 bytes). 1563 * 1563 cells * 16 bytes per cell is only around 37 megabytes (whereas 50000 * 50000 cells is something like 37 gigs!!!!).
Paths also use memory (which is why you should destroy them), and a bunch of extra memory is used during the path create call that is freed automatically before the function is over.

In terms of processing time:
Trying to find long (or non-existant) paths on very large maps can take a long time and might even cause the game to crash (which might be my fault I'm not entirely sure). That's why the path create function has an ('optional') maxdepth parameter -- if the path will take too long to find it just stops trying early and says there isn't a path.

I'm not sure what you mean by obsolete array entries. Cells are never destroyed until the whole map is destroyed (just marked as negative numbers if you can't walk on them). Paths aren't destroyed when the map is destroyed.

This grid size should be the room size divided by the cell size. If you don't need to pathfind between grids, then multiple smaller grids works better. There is a way to pathfind between multiple smaller grids to improve the pathfinding speed, but it gets very complicated (try googling Hierarchical Annotated A Star if you want to see what I'm talking about lol).

As a side note, I just realized that if you try to create a path where the goal is exactly on top of a blocked cell then the program leaks like 20 bytes of memory. This is a very small amount, but I'll fix it at some point :D
  • 1

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#9 Bleed

Bleed

    Chevalier

  • GMC Member
  • 763 posts
  • Version:GM:Studio

Posted 08 March 2013 - 01:46 AM

I got an idea: let's say we have an isometric grid map of 96,48 (my favorite btw) on it we create an A* grid of cellsize 48,24 of normal rectangular type then we path through it, but instead of assigning the return path for an object to follow we do a point_direction between the first point of the path and the second or third, to see on which direction its headed, then divide by 45
After this we just make sure to have 8 pre-defined isometric paths that move isometrically to the adjacent cells, then depending on the divided number returned we pick one of these pre-defined paths to follow.

What do you think? again theoretically speaking it should work fine.

Edited by Bleed, 08 March 2013 - 01:47 AM.

  • 0

rlztjp_zpsoqffaixe.jpg


#10 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 08 March 2013 - 07:19 AM

That theoretically sounds like it would work. This extension doesn't use game maker paths (it just returns the coordinates of the nodes in a path when asked) so some of that might be unnecessary (see the example -- the object just moves toward the next node in the "path" instead of following a game maker path). This allows you to mp_potential_step between nodes if you wish instead of just normal moving, which allows objects to still follow a general path (like through a maze or something) while using that mp avoidance around other dynamic objects.
  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#11 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 26 March 2013 - 05:52 AM

Hello I think your extention is great!

 

Could you please go into more detail on the influence map?

 

Should I create a new inf map everystep while the character is moving?

 

On a side note, when creating a map with a value if you use a number less than one, will you start to see paths change in variety?

example there are 3 hallways, instead of taking the shortest or most obvious one everytime, will the path start changing between the 3?


Edited by Archangel7x, 26 March 2013 - 07:30 AM.

  • 0

#12 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 27 March 2013 - 03:28 AM

Hi! Thanks!

 

The influence map stuff is 100% optional. You do not need to use it at all. It is supposed to provide a (somewhat) easy way to for example, mark a bunch of tiles a blocked and then unblock them easily. One use would be to, before creating a path, use influence maps to mark adjacent cells with characters in them as unwalkable, create the path, and then delete the influence maps (so these characters, who will likely move right away, don't affect the map forever). If you don't understand the influence map stuff then it might be helpful to just completely ignore it.

 

If the value is less then one then paths will tend to look like this instead of being the actual shortest path:

best-first-search-trap.png

(from http://theory.stanfo...Heuristics.html)

 

Their path might change if you change the value, but it should still be the same every time if you keep the same value.


  • 1

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#13 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 27 March 2013 - 05:15 AM

Thanks for the reply, I do understand the influence map is optional haha,

I just do not understand the proper way to use it, im using this plugin to create an ai system, I have moving ai characters but I understand that the influence map would be great for creating a path avoiding these moving characters so this ai could in turn "avoid" these objects.


  • 0

#14 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 27 March 2013 - 11:01 PM

I would do something like:

 

 

with (obj_character) {

if (other.id != id && point_distance(x,y,other.x,other.y) < SOMEDIST) {

as_inf_create(map,x div cellsize,y div cellsize,1,1,0,-1);

}

}

as_path_create(PARAMETERS)

as_inf_destroygroup(map,0);

 

EDIT:

I should mention that pathfinding and movement should be separate -- if your movement code detects a collision with a dynamic object then it should not allow that movement and tell the pathfinding code to find a new path.


Edited by Jake Armstrong, 27 March 2013 - 11:03 PM.

  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#15 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 27 March 2013 - 11:08 PM

Thanks for the reply, I have not tried that yet but I do have another question.

with as_map_setcell or rectangle I have a loop that checks for a collision in the path

for (z = 0; z < as_path_length(_vPath); z += 1){
       if !place_empty(as_path_nodex(_vPath, z) * 16, as_path_nodey(_vPath, z) * 16){
          _vColDet = true;
          _vColDetX = as_path_nodex(_vPath, z) * 16;
          _vColDetY = as_path_nodey(_vPath, z) * 16;
          
          as_map_setrectangle(argument3, as_path_nodex(_vPath, z) div 16, as_path_nodey(_vPath, z) div 16, 3, 3, -1);
          }
       }

That should set the cell it collides with as non passable right? with a width and height of 3.

 

If i am using this correctly, I cannot get this to create a new path avoiding the collision point.

 

EDIT:

EDIT:

I should mention that pathfinding and movement should be separate -- if your movement code detects a collision with a dynamic object then it should not allow that movement and tell the pathfinding code to find a new path.

Yes, but when I create a new path, it does not recognize any influence maps or impassible cells.


Edited by Archangel7x, 28 March 2013 - 01:42 AM.

  • 0

#16 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 29 March 2013 - 04:45 AM

The impassible cells should be created wherever walls are before the path is created. Marking cells as blocked that are already on the path (which is what it seems you are doing) won't affect that path because it is already generated -- I don't think you want to do this because it will then seem to break future paths "randomly" if those cells later become unblocked but you don't tell the pathfinding that. The width and height of three would make that specific cell blocked, as well as the 8 other squares down and to the right in a 3x3 square.

 

I'm not sure why it doesn't recognize the impassible cells when you create a new path. I might be able to help more if you gave more code so I could see what's going wrong.


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#17 NightGrader

NightGrader

    Game Maker Hobbyist

  • GMC Member
  • 33 posts
  • Version:GM8

Posted 30 March 2013 - 04:34 AM

Your extension is really spiffy. I really appreciated your work.

 

About the your post below. People can just try changing the camera angle.

 

Thanks so much!

I'm open to adding isometric grid support, but I'm not entirely sure what isometric grid support would be. If I was making an isometric game I would still have the game coordinates be in a traditional x, y grid and then just convert those positions to x, y screen coordinates based on the position of the fake isometric camera. For example the pathfinding/game grid would look something like:

llAemID.jpg

and then, before drawing (like in end step or something), the positions could be calculated (where xpos, ypos are grid coordinates):
 

x = (xpos + ypos)/2 * cellsize;
y = (xpos - ypos)/2 * cellsize;
depth = -y;

 

Like this:

//Camera angle change script
view_enabled = true   //Turn on View (Can be turned on at the room views section.)
view_visible[7] = true //Turns on View 7
view_angle[7] = 45     //Sets the Camera/View angle to 45 degrees

  • 0

#18 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 30 March 2013 - 09:01 PM

This could be broken atm, as it has been a few days since iv gotten into this but here we go:

(I realize I havent used arg3 yet haha)

//===============================================
/*
  argument0 = map
  argument1 = x goal
  argument2 = y goal
  argument3 = avoidmap
*/
//===============================================

_vNearestPlayer = instance_nearest(x, y, o_bot);

if _vCreatePath = true{
   as_path_destroy(_vPath);
   _vPath = as_path_create(argument0, x div 16, y div 16, argument1 div 16, argument2 div 16, global.playersize, 2, -1);
   _vCreatePath = false;
   } // End if _vCreatePath = true


if as_path_length(_vPath) > 0{
   
   for (z = 0; z < as_path_length(_vPath); z += 1){
       if !place_empty(as_path_nodex(_vPath, z) * 16, as_path_nodey(_vPath, z) * 16){
          _vColDet = true;
          _vColDetX = as_path_nodex(_vPath, z) * 16;
          _vColDetY = as_path_nodey(_vPath, z) * 16;

          as_map_setrectangle(argument0, as_path_nodex(_vPath, z) div 16, as_path_nodey(_vPath, z) div 16, 3, 3, -1);
          }
       } // End For Loop for collision point detection in path

      
   // Move to Next Node
   var vMdir, vMoveX, vMoveY;
   vMoveX = as_path_nodex(_vPath, 0) * 16 + 8; // Add 8 to get center of cells
   vMoveY = as_path_nodey(_vPath, 0) * 16 + 8; // Add 8 to get center of cells
   vMdir = point_direction(x, y, vMoveX, vMoveY);
   
   if distance_to_point(vMoveX, vMoveY) < 1{
      as_path_removefirst(_vPath);
   }
   
   phy_rotation = vMdir;
   phy_speed_x = lengthdir_x(3, vMdir);
   phy_speed_y = lengthdir_y(3, vMdir);
       
   } else{
     _vCreatePath = true;
     } // End if path has nodes

if _vColDet = true{
      as_path_destroy(_vPath);
      _vPath = as_path_create(argument0, x div 16, y div 16, argument1 div 16, argument2 div 16, global.playersize, 2, -1);
      _vColDet = false;
      } // End if Collision detected in path

Edited by Archangel7x, 30 March 2013 - 09:01 PM.

  • 0

#19 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 31 March 2013 - 12:09 AM

 for (z = 0; z < as_path_length(_vPath); z += 1){
       if !place_empty(as_path_nodex(_vPath, z) * 16, as_path_nodey(_vPath, z) * 16){
          _vColDet = true;
          _vColDetX = as_path_nodex(_vPath, z) * 16;
          _vColDetY = as_path_nodey(_vPath, z) * 16;

          as_map_setrectangle(argument0, as_path_nodex(_vPath, z) div 16, as_path_nodey(_vPath, z) div 16, 3, 3, -1);
          }
       } // End For Loop for collision point detection in path

 

This part shouldn't exist -- you don't want to make a new path if there is an obstacle anywhere along the entire path. You only want to set _vColDet to true if there is a collision immediately where the person is moving to next. You also don't want to call as_map_setrectangle unless you are going to set the cells back at some point. Also, if the cell where the path starts or where the path ends is blocked then it won't create a path (both start and goal must be walkable).


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#20 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 31 March 2013 - 09:09 PM

 for (z = 0; z < as_path_length(_vPath); z += 1){
       if !place_empty(as_path_nodex(_vPath, z) * 16, as_path_nodey(_vPath, z) * 16){
          _vColDet = true;
          _vColDetX = as_path_nodex(_vPath, z) * 16;
          _vColDetY = as_path_nodey(_vPath, z) * 16;

          as_map_setrectangle(argument0, as_path_nodex(_vPath, z) div 16, as_path_nodey(_vPath, z) div 16, 3, 3, -1);
          }
       } // End For Loop for collision point detection in path

 

This part shouldn't exist -- you don't want to make a new path if there is an obstacle anywhere along the entire path. You only want to set _vColDet to true if there is a collision immediately where the person is moving to next. You also don't want to call as_map_setrectangle unless you are going to set the cells back at some point. Also, if the cell where the path starts or where the path ends is blocked then it won't create a path (both start and goal must be walkable).

Okay, im not sure if im understanding correctly, if i just set _vColDet to true, it will just create the same path through the object im trying to path around :/, Im having a problem getting the path to not make a path through objects it shouldnt


  • 0

#21 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 31 March 2013 - 09:58 PM

You want to use as_map_setcell/rectangle to mark impassible tiles a -1 before you create the path. One way of doing this would be to have every character mark their current cell as -1, and then mark their old cell as unblocked as soon as they move to a new cell. The reason you still want to use _vColDet to possibly recalculate a path is that characters that were blocking the path when it was created might have moved in the way by the time you are halfway done moving down the path. 

 

Any pathfinding tutorial using mp_grid could be used as well, the main difference being you having to multiply and divide by the cell size (16 in this case).


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#22 Archangel7x

Archangel7x

    GMC Member

  • GMC Member
  • 236 posts
  • Version:Unknown

Posted 31 March 2013 - 10:07 PM

Ah I see, I didn't know the correct use of setcell, so it must be used before a path is created and not after? And will you go into a little detail on the influence map so I can use that correctly as well haha


  • 0

#23 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 31 March 2013 - 10:26 PM

Yea, setcell has to be used before the path you want it to affect is created.

 

Influence maps are basically just more easily reversible setcells. Rather than marking cells as impassible whenever character enters them (and passable again when they leave) like I suggested in my previous post, you could instead mark all nearby cells occupied with characters as temporarily impassible using influence maps, create the path, and then delete the influence maps.

 

eg. (from a previous post):

 

with (obj_character) {

if (other.id != id && point_distance(x,y,other.x,other.y) < SOMEDIST) {

as_inf_create(map,x div cellsize,y div cellsize,1,1,0,-1);

}

}

as_path_create(PARAMETERS)

as_inf_destroygroup(map,0);


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#24 actruncale

actruncale

    GMC Member

  • GMC Member
  • 29 posts
  • Version:GM:Studio

Posted 23 April 2013 - 02:41 AM

I've tried your example in GM Standard 1.1.929 and it doesn't work.  I am not sure if anyone else is getting this error.  I'd really like to get this to work.

 

The only thing I can debug is that as_path_length(path) is not returning a number.


Edited by actruncale, 23 April 2013 - 02:59 AM.

  • 0

#25 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 23 April 2013 - 05:34 PM

Which part isn't working? Are you getting an error message?
  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#26 actruncale

actruncale

    GMC Member

  • GMC Member
  • 29 posts
  • Version:GM:Studio

Posted 23 April 2013 - 08:37 PM

No error messages.  It just won't move the red square.


  • 0

#27 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 23 April 2013 - 10:59 PM

That's really weird. Try clicking around in the .exe version to see if it works there for you (just to make 100% sure the problem is to due to GM). You could also try uninstalling/reinstalling the extension into game maker.


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#28 actruncale

actruncale

    GMC Member

  • GMC Member
  • 29 posts
  • Version:GM:Studio

Posted 23 April 2013 - 11:03 PM

It is strange the exe version works fine.  When I put it in GM:Studio there is one error (the first room is named room not room1).  I change that but it still wont work.


  • 0

#29 actruncale

actruncale

    GMC Member

  • GMC Member
  • 29 posts
  • Version:GM:Studio

Posted 23 April 2013 - 11:10 PM

Ok I reinstalled everything and now it works... ??? I don't know what happened. lol oh well.  I am looking forward to using this.  Thanks :)


  • 0

#30 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 23 April 2013 - 11:55 PM

Thanks and no problem XD


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#31 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 24 June 2013 - 12:37 PM

Hi Jake,

 

I'm having the same problem as actruncale - I've copied everything over to GM:Studio, used exactly the scripts as in your example (with the exception of changing tile size to 32), but when I run it I get:

 

FATAL ERROR in
action number 1
of Create Event
for object obj_moving:
 
Push :: Execution Error - Variable Get 0.map(100000, 0)
 at gml_Object_obj_moving_Create_0 (line 7) - path = as_path_create(obj_map.map,x div 32, y div 32, x div 32, y div 32, width, 2, -1);
############################################################################################

 

I'm a newb so any help would be gratefully received.


  • 0

#32 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 24 June 2013 - 04:22 PM

Do you have an object named obj_map? It looks like it can't find it (obj_map should be the object that has a map variable which is set equal to as_map_create(...) )


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#33 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 24 June 2013 - 06:58 PM

Do you have an object named obj_map? It looks like it can't find it (obj_map should be the object that has a map variable which is set equal to as_map_create(...) )

 

Yes, there is an object_map, which is why I'm confused.

 

Is it because it's GM: Studio rather than 8.1?

 

I've tried uninstalling and re-installing the extension, but no joy.


Edited by benappo, 24 June 2013 - 06:58 PM.

  • 0

#34 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 24 June 2013 - 07:45 PM

The line of code in the error message you posted is trying to reference the variable "obj_map.map". Is the object actually called object_map? You either have to change the code (and all other similar occurrences of it) to "object_map.map" or more simply just rename object_map to obj_map.


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#35 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 24 June 2013 - 09:02 PM

The line of code in the error message you posted is trying to reference the variable "obj_map.map". Is the object actually called object_map? You either have to change the code (and all other similar occurrences of it) to "object_map.map" or more simply just rename object_map to obj_map.

 

Sorry, it was obj_map, not object_map, so everything should be fine - but it's not.

 

I figured out the initial issue - I'd not set the depth of obj_map to 1.

 

The code now runs, but the obj_moving does not move. Bah.

 

Code for obj_map (and this is placed on the map):

 

/// Create Map
map = as_map_create(640/32, 480/32, 1);
 
Code for obj_moving Create step:
 
/// Initialize

width = 1;
button = mb_left;

// for simplicity of example: always have a path, delete before making a new one
path = as_path_create(obj_map.map,x div 32, y div 32, x div 32, y div 32, width, 2, -1);

maxspeed = 3;

 

Code for obj_moving Step:

 

/// Path

// set new path?
if (mouse_check_button_pressed(button)) {
    as_path_destroy(path);
    
    // align to "grid" so we don't get stuck in a wall
    move_snap(32,32);
    
    path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x, obj_player.y, width, 2, -1);
}

// follow path


if (as_path_length(path) > 0) {
    // tell us to move toward first node in path
    gox = as_path_nodex(path,0)*32;
    goy = as_path_nodey(path,0)*32;
    // remove first node of path if we are close enough to it
    if (point_distance(x,y,gox,goy) <= maxspeed * 1.5) {
        as_path_removefirst(path);
    }
    
    // should we be slowed?
    var spd;
    spd = maxspeed;
    if (collision_point(x+32*width/2, y+32*width/2, obj_slow, 0, 1)) {
        spd /= 2;
    }
    
    move_towards_point(gox, goy, spd);
} else {
    // stop moving
    speed = 0;
}
It should work, shouldn't it when I press the left mouse button?
 
 

I'm stumped.

 


Edited by benappo, 24 June 2013 - 09:15 PM.

  • 0

#36 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 24 June 2013 - 10:44 PM

This line: path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x, obj_player.y, width, 2, -1);

Try obj_player.x div 32, obj_player.y div 32


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#37 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 25 June 2013 - 07:10 AM

This line: path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x, obj_player.y, width, 2, -1);

Try obj_player.x div 32, obj_player.y div 32

 

D'oh, thanks - that fixed it. 

 

I should learn to have more haste, less speed....


  • 0

#38 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 03 July 2013 - 07:58 PM

Hi Jake,

 

I'm trying to apply your A* extension to a turn-based roguelike game.

 

I'm using your extension for movement and trying to ensure that when an obj_player moves one cell, enemies also move one cell.

 

So far I'm not having too much luck. I can get the enemies to move after each move of obj_player, and they stop in a cell adjacent to the obj_player, but they move multiple cells at a time.

 

I thought I had coded a movement timer function correctly, with a movespeed decrease ticking down to 0, at which point the enemy should stop moving and should have moved one cell (32 x 32).

 

obj_moving code below:

 

Create Step:

/// Initialize


width = 1;


// for simplicity of example: always have a path, delete before making a new one
path = as_path_create(obj_map.map,x div 32, y div 32, x div 32, y div 32, width, 2, -1);


maxspeed = 4;


gridSize = 32;
moveSpeed = 4;
isMoving = false;
moveTimer = 0;

Step:

/// Path


// set new path?
if keyboard_check_pressed(vk_anykey) {
    as_path_destroy(path);
    path = path_add()
    
    // align to "grid" so we don't get stuck in a wall
    move_snap(32,32);
    
    path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x div 32, obj_player.y div 32, width, 0, -1);
}


// follow path


if (as_path_length(path) > 0) {
    // tell us to move toward first node in path
    gox = as_path_nodex(path,0)*32;
    goy = as_path_nodey(path,0)*32;
    // remove first node of path if we are close enough to it
    if (point_distance(x,y,gox,goy) <= 8) {
        as_path_removefirst(path);
    }
    
    // should we be slowed?
    var spd;
    spd = maxspeed;
    if (collision_point(x+32*width/2, y+32*width/2, obj_slow, 0, 1)) {
        spd /= 2;
    }


if (isMoving == false && as_path_length(path)-1>0 && point_distance(x,y,obj_player.x div 32, obj_player.y div 32)>32)
{
    if (point_direction(x, y, gox, goy) == 0 && obj_grid.cells[obj_player.x div 32 + 1, obj_player.y div 32] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = moveSpeed;
        speedY = 0;
    }    
    if (point_direction(x, y, gox, goy) == 180 && obj_grid.cells[obj_player.x div 32 - 1, obj_player.y div 32] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = -moveSpeed;
        speedY = 0;
    }
    if (point_direction(x, y, gox, goy) == 90 && obj_grid.cells[obj_player.x div 32, obj_player.y div 32 - 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = 0;
        speedY = -moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 270 && obj_grid.cells[obj_player.x div 32, obj_player.y div 32 + 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = 0;
        speedY = moveSpeed;
    }
  
    }
} 


if (isMoving == true)
{
    x += speedX;
    y += speedY;
    
    moveTimer -= moveSpeed;
    
    if (moveTimer <= 0) isMoving = false;
    if (moveTimer < 0)
    {
        if (speedX < 0) x += abs(moveTimer)
        else if (speedX > 0) x -= abs(moveTimer)
        
        if (speedY < 0) y += abs(moveTimer)
        else if (speedY > 0) y -= abs(moveTimer)
        
        moveTimer = 0;
    }

}

 

obj_player code:

Step:

  When not moving, check to see if a direction key is held.
   If so, assign x/y speed and change status to moving.
   Our moveDistance will be used as a count down timer.
*/
if (isMoving == false)
{
    if (keyboard_check(vk_right))
    {
        direction = 0;
        image_index = 0;
        
        if (obj_grid.cells[(x div 32) + 1, y div 32] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = moveSpeed;
            speedY = 0;
        }
    }
    else
    if (keyboard_check(vk_up))
    {
        direction = 90;
        image_index = 1;
        
        if (obj_grid.cells[(x div 32), (y div 32) - 1] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = 0;
            speedY = -moveSpeed;
        }
    }
    else
    if (keyboard_check(vk_left))
    {
        direction = 180;
        image_index = 2;
        
        if (obj_grid.cells[(x div 32) -1, (y div 32)] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = -moveSpeed;
            speedY = 0;
        }
    }
    else
    if (keyboard_check(vk_down))
    {
        direction = 270;
        image_index = 3;
        
        if (obj_grid.cells[(x div 32), (y div 32) + 1] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = 0;
            speedY = moveSpeed;
        }
    }
}


/*
   When moving, subtract from moveDistance our moveSpeed value
   and update location relevant to set speeds.
   Stop moving when moveDistance reaches zero.
*/
if (isMoving == true)
{
   x += speedX;
   y += speedY


   moveTimer -= moveSpeed;
   if (moveTimer == 0) isMoving = false;
}

The obj_player movement works perfectly, it's just the obj_moving that doesn't want to play nicely.

 

Any help with where my code is going wrong would be very much appreciated.


  • 0

#39 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 03 July 2013 - 11:31 PM

If I was making a turn based game I would probably restructure how stuff is done (because the example was meant to be for real time), but you can try if this works (added 3 lines and changed one, see comments):

// set new path?
shouldmove = false; // ADDED THIS LINE
if keyboard_check_pressed(vk_anykey) {
    as_path_destroy(path);
    path = path_add()
    shouldmove = true; // ADDED THIS LINE
    // align to "grid" so we don't get stuck in a wall
    move_snap(32,32);
    
    path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x div 32, obj_player.y div 32, width, 0, -1);
}


// follow path


if (as_path_length(path) > 0 && shouldmove) { // CHANGED THIS LINE
    shouldmove = false; // ADDED THIS LINE
    // tell us to move toward first node in path
    gox = as_path_nodex(path,0)*32;
    goy = as_path_nodey(path,0)*32;
    // remove first node of path if we are close enough to it
    if (point_distance(x,y,gox,goy) <= 8) {
        as_path_removefirst(path);
    }
    
    // should we be slowed?
    var spd;
    spd = maxspeed;
    if (collision_point(x+32*width/2, y+32*width/2, obj_slow, 0, 1)) {
        spd /= 2;
    }

EDIT: I didn't really look at your changes, but I think my code used 'maxspeed' for the speed so you can mess around with that too maybe.


Edited by Jake Armstrong, 03 July 2013 - 11:36 PM.

  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#40 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 04 July 2013 - 08:46 PM

Thanks Jake, that's almost done it. I few pathing issues, but I'll try and work on those myself.

 

Thanks for all your help.


  • 0

#41 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 05 July 2013 - 08:21 PM

I'm tearing my hair out (well I would be if I wasn't bald).

 

I still cannot get the obj_moving to move properly. They do single cell movement now, and wait for the obj_player to take its turn before moving, but the obj_moving movement is glitched.

 

It will be OK for part of a path, but stop at other parts (seemingly at random), and sometimes will get stuck in completely open space.

 

The current obj_moving code is below:

 

/// Path


// set new path?
shouldmove = false;
if keyboard_check_released(vk_anykey) {
    as_path_destroy(path);
    path = path_add()
    shouldmove = true;
    
    // align to "grid" so we don't get stuck in a wall
    move_snap(32,32)
    
    path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x div 32, obj_player.y div 32, width, 1, -1);
}


// follow path


if (as_path_length(path) > 0 && shouldmove) {
    // tell us to move toward first node in path
    gox = as_path_nodex(path,0)*32;
    goy = as_path_nodey(path,0)*32;
    // remove first node of path if we are close enough to it
    if (point_distance(x,y,gox,goy) <= 8) {
        as_path_removefirst(path);
    }
    
    // should we be slowed?
    var spd;
    spd = maxspeed;
    if (collision_point(x+32*width/2, y+32*width/2, obj_slow, 0, 1)) {
        spd /= 2;
    }
// movement of object if shouldmove = true
if (isMoving == false && as_path_length(path)-1 >0 && point_distance(x,y,obj_player.x div 32, obj_player.y div 32)>32)
{
    if (point_direction(x, y, gox, goy) == 0 && obj_grid.cells[obj_player.x div 32 + 1, obj_player.y div 32] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = moveSpeed;
        speedY = 0;
    }    
    if (point_direction(x, y, gox, goy) == 180 && obj_grid.cells[obj_player.x div 32 - 1, obj_player.y div 32] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = -moveSpeed;
        speedY = 0;
    }
    if (point_direction(x, y, gox, goy) == 90 && obj_grid.cells[obj_player.x div 32, obj_player.y div 32 - 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = 0;
        speedY = -moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 270 && obj_grid.cells[obj_player.x div 32, obj_player.y div 32 + 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = 0;
        speedY = moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 225 && obj_grid.cells[max(0,obj_player.x div 32 - 1), obj_player.y div 32 + 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = -moveSpeed;
        speedY = moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 135 && obj_grid.cells[max(0,obj_player.x div 32 - 1), max(0,obj_player.y div 32 - 1)] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = -moveSpeed;
        speedY = -moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 45 && obj_grid.cells[obj_player.x div 32 + 1, max(0,obj_player.y div 32 - 1)] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = moveSpeed;
        speedY = -moveSpeed;
    }
    if (point_direction(x, y, gox, goy) == 315 && obj_grid.cells[obj_player.x div 32 + 1, obj_player.y div 32 + 1] == 0)
    {
        isMoving = true;
        moveTimer = gridSize;
        speedX = moveSpeed;
        speedY = moveSpeed;
    }
    }
    }


    
if (isMoving == true){
    
    x += speedX;
    y += speedY;


    moveTimer -= moveSpeed;
    
    if (moveTimer <= 0) isMoving = false;
    if (moveTimer < 0)
    {          
        moveTimer = 0;
    }


}

I'm pretty sure it's something to do with the point_direction functions, but I cannot figure it out.

 

Any help would be greatly appreciated.

 


  • 0

#42 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 06 July 2013 - 12:13 AM

Hmm yea it might be a problem with the point_directions because if everything isn't aligned perfectly (or even if it is but there is float imprecision calculating the angles) then the point_directions will never be perfectly equal to the angles you are checking. You could try if (point_direction > 0 and point_direction < 90) for example, but it might be easier to do this (instead of all the point_direction if blocks):

moveTimer = gridSize;
speedX = moveSpeed*sign(gox-x);
speedY = moveSpeed*sign(goy-y);
if (obj_grid.cells[max(0,obj_player.x div 32 + sign(speedX)), max(0,obj_player.y div 32 + sign(speedY))] == 0) {
     isMoving = true;
}

If that isn't the problem, make sure there isn't something setting cells to be unwalkable and then never making them walkable again.


  • 1

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#43 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 06 July 2013 - 07:50 PM

Thanks Jake, but the neither approach works. The first just has the same glitches, and your alternative with "sign" makes the obj_moving just twitch on the spot and not move.

 

I'll think about it some more, but perhaps I need to go back to the drawing board for a step movement code.

 

Any other good ways of doing turn-based/step movement with your extension?


  • 0

#44 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 06 July 2013 - 10:48 PM

Hmm. Try this (replacing the entire step event). This is using the GameMaker built in 'direction' and 'speed' so we can eliminate possibilities for the problem. Another key difference is that the object will jump to the position they were trying to go to whenever the player releases a key before calculating an new path (this is to prevent the enemy from getting stuck in the same square if the player mashes the buttons before the moving "animation" is shown).

 

Also, is your player always aligned to the grid? If the player object isn't then the pathfinding might sometimes think the player is inside a wall when it paths so the path will fail.


if keyboard_check_released(vk_anykey) {
    x = gox;
    y = goy;
    as_path_destroy(path);
    // align to "grid" so we don't get stuck in a wall
    move_snap(32,32)
    path = as_path_create(obj_map.map,x div 32, y div 32, obj_player.x div 32, obj_player.y div 32, width, 1, -1);
    if (as_path_length(path) > 0) {
        // tell us to move toward first node in path
        gox = as_path_nodex(path,0)*32;
        goy = as_path_nodey(path,0)*32;
    }
}

if (point_distance(x,y,gox,goy) > moveSpeed) {
    speed = moveSpeed;
    direction = point_direction(x,y,gox,goy);
} else {
    speed = 0;
    x = gox;
    y = goy;
}

  • 1

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#45 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 07 July 2013 - 07:47 PM

Thanks for all your help Jake, but using the new code, I just get an error:

 

 
___________________________________________
############################################################################################
FATAL ERROR in
action number 1
of  Step Event0
for object obj_moving:
 
Push :: Execution Error - Variable Get -1.goy(100014, 0)
 at gml_Object_obj_moving_Step_0 (line 16) - if (point_distance(x,y,gox,goy) > moveSpeed) {
############################################################################################
 

 

The obj_player step code is below - it does snap to grid after every key press:

 

if (isMoving == false)
{
    move_snap(32,32)
    if (keyboard_check(vk_right))
    {
        direction = 0;
        image_index = 0;
        
        if (obj_grid.cells[(x div 32) + 1, y div 32] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = moveSpeed;
            speedY = 0;
        }
    }
    else
    if (keyboard_check(vk_up))
    {
        direction = 90;
        image_index = 1;
        
        if (obj_grid.cells[(x div 32), (y div 32) - 1] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = 0;
            speedY = -moveSpeed;
        }
    }
    else
    if (keyboard_check(vk_left))
    {
        direction = 180;
        image_index = 2;
        
        if (obj_grid.cells[(x div 32) -1, (y div 32)] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = -moveSpeed;
            speedY = 0;
        }
    }
    else
    if (keyboard_check(vk_down))
    {
        direction = 270;
        image_index = 3;
        
        if (obj_grid.cells[(x div 32), (y div 32) + 1] == 0)
        {
            isMoving = true;
            moveTimer = gridSize;
            speedX = 0;
            speedY = moveSpeed;
        }
    }
}


/*
   When moving, subtract from moveDistance our moveSpeed value
   and update location relevant to set speeds.
   Stop moving when moveDistance reaches zero.
*/
if (isMoving == true)
{
   x += speedX;
   y += speedY


   moveTimer -= moveSpeed;
   if (moveTimer == 0) isMoving = false;
}

  • 0

#46 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 07 July 2013 - 08:58 PM

It looks like it might be an error because gox and goy aren't set. Put gox = x; goy = y; in the create event.


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073


#47 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 08 July 2013 - 09:00 PM

D'oh, yes, no gox and goy variables set.

 

Now set - and everything works perfectly.

 

Many thanks for all your help.


  • 0

#48 benappo

benappo

    GMC Member

  • GMC Member
  • 13 posts
  • Version:GM:Studio

Posted 15 July 2013 - 08:07 PM

OK, now I'm trying to code the obj_moving collision event with the obj_player.

 

So far I have:

 

//collision event with player
if (place_meeting(x,y,obj_player))


{
// in collision event with obj_player...
    var_dir = point_direction(x,y,obj_player.x,obj_player.y)
    x = x+lengthdir_x(-32,var_dir)
    y = y+lengthdir_y(-32,var_dir)
    moveSpeed = 0
    
}

I had assumed that each turn the obj_moving,if colliding with the obj_player, would "bounce" back one cell (32,32) in the direction it came from. It kind of does it, but the obj_moving will sometimes jump back in different directions, or into walls.

 

What can I do to ensure then enemy continues to "bump" into the player each turn, but doesn't jump around like a manic frog?


  • 0

#49 DisBeGee

DisBeGee

    GMC Member

  • GMC Member
  • 14 posts
  • Version:Unknown

Posted 23 July 2013 - 06:54 AM

I'm having a small problem here too...

 

I'm building an RTS and when I place a building using as_map_setcell(). When I build a new building, game maker completely CRASHES. I have the game running in debug mode and when I exit out after it crashes, game maker won't go back to the programming interface again; it's so weird. If I don't save, I lose my work.

 

I've isolated it to the as_map_setcell() of the Create event of the building, because when I disable it it doesn't happen anymore

 

The thing that confuses me though is that I already have prebuilt buildings on the map and the as_map_setcell() works perfectly. But when I create a NEW building, it crashes everything??? I just wanted to put this here, seems very bizarre and nothing I've ever seen before, maybe somebody else could replicate it easier


  • 0

#50 Jake Armstrong

Jake Armstrong

    GMC Member

  • GMC Member
  • 510 posts
  • Version:GM8.1

Posted 23 July 2013 - 07:17 PM

DisBeGee:

That's really weird I've never seen anything like that. I don't know why anything would cause a crash, but you could check if maybe you are trying to set cells that are either outside of the map or you are trying to set cells of a map that doesn't actually exist (so the program might try to access invalid memory). You could also check your total RAM usage with task manager when it crashes to see if that has something to do with it. If you can't figure it out and your code isn't secret you could show me some and I could try to help you more.

 

benappo: 

Yea I'm not really sure what the problem could be but it probably has something to do with using point_direction and lengthdir. Because you have a square grid, if the distance between horizontal/vertical squares is 32 then the distance between diagonal squares is something like 45.25. It would probably be easier to just store the previous cell the object was in and return to it if they run into the player.


  • 0

A star pathfinding extension (fast, variable cost tiles, multi-tile objects): http://gmc.yoyogames...howtopic=570621

Multiple mice extension http://gmc.yoyogames...howtopic=575963
extension to check if game is in focus (vs. being alt tabbed, etc.): http://gmc.yoyogames...howtopic=549073