LoginLogin
Nintendo shutting down 3DS + Wii U online services, see our post

enemy AI which would go through a maze and find the player

Root / Programming Questions / [.]

ChaseCZCreated:
I should have added this for my first post in this thread. https://en.wikipedia.org/wiki/A*_search_algorithm It is going to explain things much better than I can. Anyway, you have inspired me to go back and fix up my old broken A* program to get it working. If you look at the above URL you may notice that my code and the pseudo code in the wikipedia link are very similar. You can download my test program with the key KRD373AE, it may not be up forever so get it while you can. If you run the program you should see something like this. The white blocks are impassable. The black tiles are normal passable floor. The green squares are places that have been added to the "Open list" and are for consideration as an optimal path. The red tiles are in the closed list they were considered and unless they are on the final path were rejected as being not-optimal. Finally the magenta squares are the path the program chose. You don't need a sprite for a node. In this example each square in the map is a node. Edges are implied to be the four cardinal directions (North, East, South, West) where available from each tile. This is actually quite wasteful and slow. If you have ever heard the term navmesh in games. They basically make a low resolution net of x and y (and z) coordinates on the map that connects sections of the map together without bumping into walls and the like. This will vastly reduce the processing required to path find over a large map. You could just have a set of x, y coordinates and links to neighboring nodes and the distance to travel between them. You can also add more or less cost to a path if the unit would be going up or down hill or over rough/smooth terrain. In my example it costs exactly 1 unit to travel from one square to another neighboring square. The heuristic is important, it is basically the program giving a guess as to how far away the target is from the goal. The trick is you don't want to over-estimate the amount or you could end up with non-optimal paths like this. The path would have been more efficient if it went above the wall on the left instead of going down around and back up the other end. If you have a really bad heuristic, you might end up evaluating just about everything in a flood-fill type manner. A more efficient path would look like this: Of course you will notice that we evaluated a lot more nodes to get the optimal path. The better heuristic also uses the square root function to get distance using the Pythagorean theorem (he just keeps coming up in this thread doesn't he) which is very slow. As I said earlier in the thread you don't want to run this every frame. Anyway, give the above wikipedia article a read and let me know if you have questions. You may be in over your head if you haven't gotten friendly with things like arrays yet however. Oh, and as a bonus the map is loaded from data strings as discussed earlier. Maybe that will help too. Not my best code, so let me know if you find any bugs or have questions for me if you read the code. Now that I have A* working maybe I should go back and work on Combat 3-D some more. Javidx9 on Youtube has covered A* as well as Wave Propagation Path Planning. If you don't mind some C++ code, they are both well worth watching. Wave Propagation https://www.youtube.com/watch?v=0ihciMKlcP8 A* https://www.youtube.com/watch?v=icZj67PTFhc It looks like the Coding Train has done a video on A* too. https://www.youtube.com/watch?v=aKYlikFAV4k
Wow, thanks! That's a cool program, but since it's gonna be a 2D platformer without jumping, i guess i'll just go with the door chooser, because i'm super bad at math (and i hate it too lol) and i don't understand a single function used in the program lmao So, i guess i will need help with the arrays but idk where to start huh
Here is a good place to learn about arrays: link But the problem I'm having with this is understanding the code. It's all just setting variables, but I don't know what any of the variables mean. Would you please be more clear about that?
Oh yeah, thanks. I think it's not that difficult to understand, i actually still don't understand how do i store maps into arrays and how do i find a certain tile or point using that much

-SNIP-
Wow, thanks! That's a cool program, but since it's gonna be a 2D platformer without jumping, i guess i'll just go with the door chooser, because i'm super bad at math (and i hate it too lol) and i don't understand a single function used in the program lmao So, i guess i will need help with the arrays but idk where to start huh
Here is a good place to learn about arrays: link But the problem I'm having with this is understanding the code. It's all just setting variables, but I don't know what any of the variables mean. Would you please be more clear about that?
Oh yeah, thanks. I think it's not that difficult to understand, i actually still don't understand how do i store maps into arrays and how do i find a certain tile or point using that much
So there are a few ways you can store a map in an array. You can do it in a convenient way if you are using DATA. You would have a map table array that can have multiple element; you might want at least 10 different map tiles depending on what type of map you are making. The BG table stores what you would set the BG tiles to inside of an array. Then you have your data. You would have a repetition of strings read into a string array, MAP$[MAP_HEIGHT]. You would represent these strings with the DATA instruction. Beforehand, you would want to set your BG table. If you want less than 10 different tiles, that's fine. If you want more, that's fine too. It just might change the way you represent this in your strings. Then in your strings, you would put your map. I normally represent this with numbers and above characters, but you can do this however you want, like starting with the letter A. This will change how you need to read the map. Then you put your map. In strings using DATA, you put down the characters in the map that you want. Now you need to read it. This can be done with a FOR loop and a few string functions. You put an X loop that goes from 0 to the map width-1. Then you put a Y loop around that so that it loops X multiple times. Then you have a function that reads strings. (MID$ is a good one) You then subtract the minimum character code (for me it would be ASC("0") because I start with 0, but it can be different) and search the new number in your BG table. Then you use BGPUT to put the bg tile where it goes on the screen. You can tell where to put it because that's where it is in the FOR loop. That's about it. If I didn't explain this well enough, feel free to ask questions. There probably are different ways to do maps with DATA, Seggiepants might have used a different way, but this is the way I learned and use. Then you could use a 2D-integer array (DIM MAP%[5,5]) If you don't know how that works with maps specifically, it's just a 2 dimensional array with X and Y flipped, ARRAY[HIGHT,WIDTH]. You simply fill it with the array tile's numbers, and then load it to the screen with BGLOAD. This is the way the MAP tool saves maps in the Smile tool. There may be other ways to make maps with data arrays, but I've only payed attention to these because I find them very useful. Please ask any questions you may have about this. And with finding a point in the integer array, you just search for the point: ARRAY[SEARCHY,SEARCHX] As for the string array, I haven't found a need to do that yet, so I don't quite know.

Or you could use
DIM MAP$[5]
so you can use strings, which makes it much easier to read and you can use characters in any case.

Or you could use
DIM MAP$[5]
so you can use strings, which makes it much easier to read and you can use characters in any case.
umm I did the string array with the DATA instruction as a way to read it

Yeah, like that

yeah that was included in my post.

-SNIP-
Wow, thanks! That's a cool program, but since it's gonna be a 2D platformer without jumping, i guess i'll just go with the door chooser, because i'm super bad at math (and i hate it too lol) and i don't understand a single function used in the program lmao So, i guess i will need help with the arrays but idk where to start huh
Here is a good place to learn about arrays: link But the problem I'm having with this is understanding the code. It's all just setting variables, but I don't know what any of the variables mean. Would you please be more clear about that?
Oh yeah, thanks. I think it's not that difficult to understand, i actually still don't understand how do i store maps into arrays and how do i find a certain tile or point using that much
So there are a few ways you can store a map in an array. You can do it in a convenient way if you are using DATA. You would have a map table array that can have multiple element; you might want at least 10 different map tiles depending on what type of map you are making. The BG table stores what you would set the BG tiles to inside of an array. Then you have your data. You would have a repetition of strings read into a string array, MAP$[MAP_HEIGHT]. You would represent these strings with the DATA instruction. Beforehand, you would want to set your BG table. If you want less than 10 different tiles, that's fine. If you want more, that's fine too. It just might change the way you represent this in your strings. Then in your strings, you would put your map. I normally represent this with numbers and above characters, but you can do this however you want, like starting with the letter A. This will change how you need to read the map. Then you put your map. In strings using DATA, you put down the characters in the map that you want. Now you need to read it. This can be done with a FOR loop and a few string functions. You put an X loop that goes from 0 to the map width-1. Then you put a Y loop around that so that it loops X multiple times. Then you have a function that reads strings. (MID$ is a good one) You then subtract the minimum character code (for me it would be ASC("0") because I start with 0, but it can be different) and search the new number in your BG table. Then you use BGPUT to put the bg tile where it goes on the screen. You can tell where to put it because that's where it is in the FOR loop. That's about it. If I didn't explain this well enough, feel free to ask questions. There probably are different ways to do maps with DATA, Seggiepants might have used a different way, but this is the way I learned and use. Then you could use a 2D-integer array (DIM MAP%[5,5]) If you don't know how that works with maps specifically, it's just a 2 dimensional array with X and Y flipped, ARRAY[HIGHT,WIDTH]. You simply fill it with the array tile's numbers, and then load it to the screen with BGLOAD. This is the way the MAP tool saves maps in the Smile tool. There may be other ways to make maps with data arrays, but I've only payed attention to these because I find them very useful. Please ask any questions you may have about this. And with finding a point in the integer array, you just search for the point: ARRAY[SEARCHY,SEARCHX] As for the string array, I haven't found a need to do that yet, so I don't quite know.
Thanks very much, i'll try it out and then let you know, if i don't understand something or something just won't work right

Also, if you want to read tiles that are on the screen, BGGET is useful.

Also, if you want to read tiles that are on the screen, BGGET is useful.
Yes, i figured that out already. Good for collision detection e.g.

Try the A* algorithm

Try the A* algorithm
Yeah we talked about that quite a bit here already We should talk about it more though, because I'm a bit confused at how to implement it.

This may be simpler to implement if on a grid based map: Starting at zero where the player stands, you will have the program number every tile according to the following rules: every square is numbered incrementally following paths out from the player (0 1 2 3 4...) Where 2 paths converge, the one with the lower number takes precedence and the increments continue from its value. Once a number has been written on a tile it may not be overwritten. This should continue until the whole map is covered Then have the enemy go the direction with the lowest numbered tile I literally just thought of this idk if it is 100 percent efficient path chooser (I think it is) but someone has probably invented this method before

#######
#54323#
#4##1##
#321P1#
#4#####
#56789E
#######
Like that (😂 took so long to do from phone)

#######
#54323#
#4##1##
#321P1#
#4#####
#56789E
#######
Like that (😂 took so long to do from phone)
I'm not exactly sure that that's a*, because I'm pretty sure that a* is where you have a grid with edges representing distance between edges. Then the AI finds the shortest path by moving along the nodes in the grid, and bases that path off of a heuristic function. I'm not exactly sure how this works, or how to implement it though.

#######
#54323#
#4##1##
#321P1#
#4#####
#56789E
#######
Like that (😂 took so long to do from phone)
Sounds like wave propagation, just remember to start at E and work backward to P so you don't go in circles. Any reason you don't look at the code I provided (KRD373AE) or the YouTube videos or the wikipedia page or just ask a implementation question if you are having problems with A*? A* is normally college level material so don't feel bad if it takes a while to get a hang of. Personally I would probably simplify your idea and make the monsters dumb before I invested too much time in AI.

Any reason you don't look at the code I provided (KRD373AE) or the YouTube videos or the wikipedia page or just ask a implementation question if you are having problems with A*?
I did look at them and it's still kinda hard to understand. But I shall look again since it's been a while, and I have gained new knowledge. EDIT: Ok, now that I look back at it, it makes much more sense! Thank you for reminding me about those links!

#######
#54323#
#4##1##
#321P1#
#4#####
#56789E
#######
Like that (😂 took so long to do from phone)
That's simplest pathfinder, and will often get the job done. Thiugh only try to find path every 'x' frames, or more often when closer to the player.

#######
#54323#
#4##1##
#321P1#
#4#####
#56789E
#######
Like that (😂 took so long to do from phone)
I'm not exactly sure that that's a*, because I'm pretty sure that a* is where you have a grid with edges representing distance between edges. Then the AI finds the shortest path by moving along the nodes in the grid, and bases that path off of a heuristic function. I'm not exactly sure how this works, or how to implement it though.
Yeah that's not the a* algorithm I just suggested that because that may be simpler to implements for a beginner