Відео

That extra line that visual studio adds to the end of a file, that should be a preference option that can be turned off. However, this will impact the way git calculates and displays commit diffs in a way that is suboptimal.

floyd warshal? looks pretty close to me

I know this approach as a flowfeild, its single pass BFS out from the "enemy" and is more common on RTS games, as you effectivly solve outwards from all targets, and then the units will path to the nearest unit (lowest iteration number from the BFS) to "fight" the lazy approach is find all untouched neightbourds (as you can move diagonal its up to 8), and point to that cell and have an iteration count, then find there untouched neightbours and point to that cell and so on, this fixes the neutral pressure issue, and the iteration count keeps updates cheap, as you only need to propegate a partial update from the site,

My man that's called flood fill, or at least a variation of it and yes that seems more in line with what you need for large number of pathfinding entities as they can use the gradient mesh for path finding on a low refresh rate. A* is optimized for a different thing which is a singular path from point a to b and should blow your algorithm away when doing that for massive grids. Like scale your grid up to 10 million nodes and watch it be almost instant compared to your implementation to find a singular path from point a to b. Banger vid though!

19:56 It's because your for loops are inside your function. It's not more simple, just hidden

A* is specifically built to take the shortest path while avoiding calculating as many extra steps as it can to keep the search time as low as possible. By making A* search the whole map you are literally taking it and making it do exactly what it is built to avoid doing. So obviously a simple breath-first search is going to be more efficient than it because that is exactly what BFS is designed for. Although I have to admit this is quite a novel way to think about BFS.

16:17 This is so spaghetti... Instead if (x == 0 && y == 0) { if (!Position....) return ... if (!Position...) return ... ... return ... } else return ... No ternary needed. Also way more readable. Also I think you can simplify x and y declarations by casting the booleans to ints. Which I think true casts to 1?

I think i saw a glimpse of 3blue1brown's vector animation.... xD

1:08 hans slander

I'm not a native Japanese speaker, but your Japanese accent reminded me of those bad English accent lines that Japanese seiyuu sometimes do in anime, just in reverse. 😂

The operators are yellow because they are overloaded. When the operator is the original object.op_equality then its white, and when the class overrides it then it becomes yellow. Its not very obvious detail in VS.

8:05 Since cat was meant for, well, concatenation, it doesn't add a line feed after printing a file to the console But people use cat to read their files, so they started manually adding that line feed at the end of theirs so their shell doesn't look messed up after cat diff explicitly states when a file doesn't end with a line feed for this reason, same for VS adding it

This is world partitioning basically. A common solution to physics and detection of all kinds in computer science.

7:19 whys he edging us like that

did you reinvent dvorjak ?

The CIA requests your location.

15:14 well you could improve it by moving the if check at the end above the defaultPathVector calculation. no clue if java would optimize that but fairly low hanging fruit

something you could try for faster pathfinding is doing multi-layer or hierarchical flow fields. basically, at a distance, when the player moves, the best path is the same for 90% of it, so if you do it at a large grid cell and a small grid cell, you could have the large scale grid update less often because it takes longer for the player to traverse it, and only calculate the small scale for a smaller area. then stuff could first pathfind with the large grid before switching to the small grid once it gets close enough.

The general gist kinda reminds me a bit of what they used on LiquidWar

A similar concept to following this "pressure vector" mechanic, is making the field be an "integer distance to nearest target" and just walk in what ever direction has lower numbers. This alternate scheme will generally not have the misdirection problem mentioned around @5:00

This looks simmilar (to me, I spent 5 minutes to find it): How do vector field Pathfinding algorithm work ? @pdn-pasdenom4979 watch?v=ZJZu3zLMYAc

1:13 Hans Niemann's butt plug?

Instructions unclear:The mobs have found my house, Send help.

A* is a modified version of Dijkstra's, to work faster for single locations, you are rediscovering Dijkstra's (BFS) which is honestly impressive AF

definitely an interesting approach to path-finding. though i do wonder: isn't this just flood fill with extra steps?

Here for the training arc prepping for when Thomas inevitably gets isekai’d into a world where common pathfinding algorithms aren’t already discovered. Let me know when you become god of the new world :D

38:23 bro just made air

Sorry, but you still got a minor thing wrong with percentages. 1 is equals to 100%. Because % is just per one hundred. So multiplying it by 100 is wrong.

flood fill

Arrows arrows arrows not surprised

that intro was so cringe

God before time existed:

Ok. But isn't there like 10 different ways to do it even better than this? This feels extremely intensive for large maps and such, unless we're putting an upper limit on the range pathfinding can have. I'm gonna be honest, I didn't watch the whole video because you sort of dragged on really slow for me. Not saying it's a bad video or anything, I think you explained things quite well from what I saw. Just wasn't my cup of tea when it came to pacing. Carry on and good luck.

"So simple"

getting caught with your hand in your pants is crazy and im stealing it 25:22

grate video, i think you might be the first to implement a BFS in to a game pathfinder

they cry about AI because they are scared of the fact that ai brakes the "coding" barrier in real world problem solving and now they have to compete with all the problem solving monsters who did't learn coding cause "i already have lambda".

I like the way the arrows being slowly drawn instead of just popping out. Btw your Japanese accent was good, and it match quite well with the scene, but still need some stress (emphasis) at certain parts to show the impact. The best part is "Use a vector field!". For the text at the beginning, you should use 前回 (previous episode). 先に usually means "firstly" "ahead of" "before".

Good job. You effectively rediscovered BFS. I recently did the same

These vids are great dude, keep it up

Flow fields! I'm surprised at it being computationally cheaper overall, but I have seen this used in 2D pathfinding as an optimization for groups of mobs! Instead of multiple agents all doing an individual A* query, you generate the flowfield occasionally (1hz is fine usually), and the agents can all just use it as a "map"!

You should take a look at flow field pathfinding, I learned about it in relation to pathfinding with robotics. Seems to me you've found your own way to generate a flow field. As for your first approach of random sampling, there's a great deal of research in that too, and an algorithm like RRT* is a very well known example of this, maybe it could be interesting for you to look at!

Like

Hi, first of all, I wanted to say that I love your enthusiasm when it comes to learning about the basic concepts of programming. Many people today think programming is about using drag-and-drop in Unity to design a map and then using ChatGPT to create a script that makes the player move. But I think programming is about finding cool algorithms like yours and testing them against high-end algorithms. That said, I really enjoyed your video, but sadly, I think you came to the wrong conclusion. So please let me try to convince you that you gave up on standard pathfinding algorithms a little too quickly. First of all, allow me to help you optimize your algorithm. Instead of calculating vectors for every tile in your grid, just calculate the distance to the origin. To do this, use your origin as the starting point and perform a breadth-first search to assign every tile its value. If you now want to pathfind from any tile in the grid, just check all neighbors for the smallest number-that's the fastest way to the origin. This way, you don't need to spend so many float operations on your vectors, which are a little overkill if you're using a 2D grid. This algorithm also has a name-it's called the Dijkstra algorithm and is a predecessor of the A* algorithm. So your basic concept is pretty good-there are just a few unnecessary bits here and there. But sadly, there are also a few reasons why it probably won't work in a video game. First of all, you mentioned that A* struggles when the terrain changes or the player moves. That's true, but it's also true for your algorithm. I think your idea was that if you used walls as "pressure generators," you wouldn't need to reprocess adjacent vectors when map changes occur in different parts of the map. But that's not realistic. If the map changes, how would you determine which vectors need to be updated and which don't? A*, or even Dijkstra, doesn't have this problem since it only updates tiles that need to be updated. But there's an even bigger problem. Your algorithm only works if you calculate the pressure vector for basically every tile in your world. If you implement this in a video game with potentially thousands of tiles, it's never going to perform well. The same applies to Dijkstra, and even to A* to a certain degree. Sadly, even with modern technology, we can't calculate everything we want. It's impossible to input a gigantic grid and expect good results from Pressure Pathing, A*, or any other algorithm. Video games today use many tricks to compensate for this issue. For example, they preprocess waypoints that are already known on the map. This way, the algorithm doesn't need to work on the entire world grid but just within a small room, from one door to the other. If there are a large number of enemies, you can perform pathfinding for the first one and have the others follow. Pathfinding is an interesting puzzle, and to solve it, you need more than one singular algorithm. I really hope I made my point clear without offending you. As I said earlier, I enjoy working out these basic algorithms just like you do, and I hate it when I realize my solution is not better than the standard libraries. But at least for me, that doesn't take away the fun of coding it out.

Darn. Second comment. Oh well good job! 😄

Seems like a promising approach, but maybe it doesn't scale well? Have you tried it on much larger grids? I'm aware you've done the big O notation stuff, but maybe it an unexpected result is to be found at higher size grids?

Happy New Year everyone! (yeah I'm a couple weeks late; what're you gonna do about it?) If you haven't already, go to the poll on my channel (link: www.youtube.com/@ThomasWaldYT/community) or reply to this comment to vote whether or not you prefer watching me build projects from scratch. Peace! Edit: Yep, so as some comments have pointed out, I've effectively rediscovered flow field pathfinding here. That "random guy's blog" from the video, Red Blob Games, actually has a post about it (www.redblobgames.com/blog/2024-04-27-flow-field-pathfinding/) from last year on my birthday. Go figure. I will never discover anything unique, and I accept my fate. 😂🥲

22:11 i'm just looking around and indentifying elements, one cursed thing i saw is what would be Hydrogen 6, which would fall apart basically as soon as it started to exist irl

wow i watched the first minute and i already love this gigachad smart guy with his sick shades