enemy AI which would go through a maze and find the player
I would calculate the door to enter from with the Pythagorean Theorem. For a right triangle with sides a, and b and hypotenuse c it states that a^2 + b^2 = c^2. Let x1, y1 be the location the monster was (globally) at when you left them. Then for each door in the current room let x2, y2 be the (global) location of the door. dx = x2 - x1, and dy = y2 - y1 so calculate dx*dx + dy*dy and use the door that has the smallest resulting c^2 value. All that being said, having a monster chasing you from room to room is pretty non-standard game behavior. I can't think of many games that do it, as it is pretty brutal. So I would of course use it very sparingly.Yes, that could work, but i actually think i have another problem... I'm kinda trying to remake a PC game and the monster screams (a lot lmao) when approaching the player and i want the sound of it screaming get louder the closer the monster gets to the player, just so it to be accurate and actually spice it up a bit. Not to mention there are much more monsters that chase the player through rooms (but they work a little differently) and will probably need at least some simple path finding algorithm. Don't wanna say how exactly they would work because that would spoil a lot (but you can could already tell what am i actually trying to remake by now). Some of you might say that you can't help me if you don't know how the other monsters are supposed to work but it would be totally sufficent if you helped me the first monster we're talking about. By the way thanks very much for all the help i got by now
You can set the noise of a beep like this:Yes, i know how to do that. But how would i measure the distance between the player and the monster, if the monster is gonna teleport to the player at some point (without the monster approaching the player)'Which beeping, pitch, volume(0-128, 64 is default) Beep 5, 200, 84
Subtract the monster x and y values from the player.Wait i can actually do that with the timer + the time it takes for the monster to reach the player in the room... But there's still other monsters, which can't just work by teleporting to the room, where the player is... The A* algorithm looks sufficent but after reading all the explanations i found online (including the one you sent me), i still don't get how to actually code it lol
I would a^2+b^2=c^2 it.
Have one point of the right triangle be the player and another point be the enemy. Draw the lines to a point (PX,EY or EX,PY PX/PY being player and EX/EY being enemy) and find c. Then reflect that across 0 and add 127 for the volume.
I may have described this wrong, so I'll make a test program.
K here:
K8XJ3WD
just focus on how I made the sound get louder as it gets closer.
I would a^2+b^2=c^2 it. Have one point of the right triangle be the player and another point be the enemy. Draw the lines to a point (PX,EY or EX,PY PX/PY being player and EX/EY being enemy) and find c. Then reflect that across 0 and add 127 for the volume. I may have described this wrong, so I'll make a test program. K here: K8XJ3WD just focus on how I made the sound get louder as it gets closer.Yes that's a pretty cool program, but the problem is that at some point a timer is gonna run and after that timer the monster is gonna teleport to some door in the player's room (depending on where the monster initially spawned) so that's kinda useless for that. I think i'll rather store every door the player walks in and then make the monster go the same path
Any reason you can't keep the whole map in memory and just A* for the monster AI. That might work better.
I think the Pythagorean formula actually works better for the distance based volume than it does for the door chooser. I would have a maximum (squared) distance. If the distance is larger than that don't play a scream. Otherwise do a linear interpolation to map distance to volume and use that instead. Zero distance = max volume, maximum distance = minimum volume.
Any reason you can't keep the whole map in memory and just A* for the monster AI. That might work better. I think the Pythagorean formula actually works better for the distance based volume than it does for the door chooser. I would have a maximum (squared) distance. If the distance is larger than that don't play a scream. Otherwise do a linear interpolation to map distance to volume and use that instead. Zero distance = max volume, maximum distance = minimum volume....and how do i store the entire map into a variable? Lol
How about using a 2 dimensional array DIM map[MAP_HEIGHT, MAP_WIDTH]? You could also use an array of strings DIM map$[MAP_HEIGHT] where each string in the array is MAP_WIDTH characters long. If you are willing to do a bit of math you could say DIM map[MAP_HEIGHT * MAP_WIDTH] and if you want location x, y it is map[y * MAP_WIDTH + x]. Similarly you could have a string of MAP_HEIGHT * MAP_WIDTH characters and again say MID$(map$, y * MAP_WIDTH + x, 1).
Of course if you whole map fits in the BGSCREEN's 16383 tile maximum (just under 128x128 tiles) you could just read it from there too.
If you have problems with arrays let me know, and I can try to explain.
How about using a 2 dimensional array DIM map[MAP_HEIGHT, MAP_WIDTH]? You could also use an array of strings DIM map$[MAP_HEIGHT] where each string in the array is MAP_WIDTH characters long. If you are willing to do a bit of math you could say DIM map[MAP_HEIGHT * MAP_WIDTH] and if you want location x, y it is map[y * MAP_WIDTH + x]. Similarly you could have a string of MAP_HEIGHT * MAP_WIDTH characters and again say MID$(map$, y * MAP_WIDTH + x, 1). Of course if you whole map fits in the BGSCREEN's 16383 tile maximum (just under 128x128 tiles) you could just read it from there too. If you have problems with arrays let me know, and I can try to explain.Alright. thanks for your help, i'll have to check the arrays first, but i'll let you know when i get stuck again... Which leads me to another problem/s... I planned to make the doors sprites, but there's a way to place the door as a background tile and then change it according to variables holding the values of it's position when the background is gonna move as the player is gonna move and i don't really know how would make the monster actually pick and enter the right door which would lead him to the player, so idk if sprites or bg tiles would be better for this scenario
You could also use an array of strings DIM map$[MAP_HEIGHT] where each string in the array is MAP_WIDTH characters long.This is my favorite way to do this bc. you can apply the DATA instruction and keep all your stuff in the same place. It's also how I learned to make maps with the DATA instruction (idk if there is another way to use DATA for maps lol) And it's really easy to edit without opening other programs to edit all the map data.
Also I kinda understand A* lol
And by that I mean I understand Djikstra's pathfinding algorithm.
Basically you have your nodes (I would have those be the corners and where the path splits into more than one path) and your edges (I would make them the direct path between two nodes without a wall). You would also have the enemy location be a node. The enemy node would be the source node. Then you need a destination node. That would be where the player is. First I would clear the enemy path array, which I would use as the locations the enemy would go straight to when the path is figured out..Then you calculate the smallest distance between the source node and it's surrounding nodes (at max 4 if you have it as a grid, which is probably the best option). After this, you travel to the closest node, and cross out the last one. I wouldn't move the enemy yet though, we are still trying to figure the whole rout. I would just add this location to your route array we talked about earlier. We would then repeat the stuff with finding the shortest path and adding it to our route, until we reach our destination. Then we would have our heuristic function magic. I don't understand this much yet, but this is what makes Djikstra's method the A* algorithm. What I know about it is kinda background about which paths get you where you are going, like what direction the goal is in, but I'm not completely sure yet. I will be thankful if someone could go into more depth on that, so that I can get my head around it.
Also I kinda understand A* lol And by that I mean I understand Djikstra's pathfinding algorithm. Basically you have your nodes (I would have those be the corners and where the path splits into more than one path) and your edges (I would make them the direct path between two nodes without a wall). You would also have the enemy location be a node. The enemy node would be the source node. Then you need a destination node. That would be where the player is. First I would clear the enemy path array, which I would use as the locations the enemy would go straight to when the path is figured out..Then you calculate the smallest distance between the source node and it's surrounding nodes (at max 4 if you have it as a grid, which is probably the best option). After this, you travel to the closest node, and cross out the last one. I wouldn't move the enemy yet though, we are still trying to figure the whole rout. I would just add this location to your route array we talked about earlier. We would then repeat the stuff with finding the shortest path and adding it to our route, until we reach our destination. Then we would have our heuristic function magic. I don't understand this much yet, but this is what makes Djikstra's method the A* algorithm. What I know about it is kinda background about which paths get you where you are going, like what direction the goal is in, but I'm not completely sure yet. I will be thankful if someone could go into more depth on that, so that I can get my head around it.Thank you very much. I think i'm starting to understand it. And for the nodes, i could use some invisible sprites (the player and enemy nodes would be their own sprites) and i would then calculate the distance between each node to reach the player, right? I doubt this is the only way, but it's just what i thought wouldn't be a bad idea
It could be a good idea, the only problem with this is that you can only have 512 nodes, including the player and enemy. The way I would do it is to have an array containing all of the node's positions, and have a function that calculates which nodes the AI can go directly to. That would be an edge. Either way probably works, just the array is more fit for bigger maps.Also I kinda understand A* lol And by that I mean I understand Djikstra's pathfinding algorithm. Basically you have your nodes (I would have those be the corners and where the path splits into more than one path) and your edges (I would make them the direct path between two nodes without a wall). You would also have the enemy location be a node. The enemy node would be the source node. Then you need a destination node. That would be where the player is. First I would clear the enemy path array, which I would use as the locations the enemy would go straight to when the path is figured out..Then you calculate the smallest distance between the source node and it's surrounding nodes (at max 4 if you have it as a grid, which is probably the best option). After this, you travel to the closest node, and cross out the last one. I wouldn't move the enemy yet though, we are still trying to figure the whole rout. I would just add this location to your route array we talked about earlier. We would then repeat the stuff with finding the shortest path and adding it to our route, until we reach our destination. Then we would have our heuristic function magic. I don't understand this much yet, but this is what makes Djikstra's method the A* algorithm. What I know about it is kinda background about which paths get you where you are going, like what direction the goal is in, but I'm not completely sure yet. I will be thankful if someone could go into more depth on that, so that I can get my head around it.Thank you very much. I think i'm starting to understand it. And for the nodes, i could use some invisible sprites (the player and enemy nodes would be their own sprites) and i would then calculate the distance between each node to reach the player, right? I doubt this is the only way, but it's just what i thought wouldn't be a bad idea
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
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
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.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?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.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