Farer

So interesting !

I made custom pathfinding solution before. How about considering my project too ?

https://github.com/Farer/bw_path_finding

I really dislike extreme views. 0 or 1. This is a concept that only fits the Digital world. The world we live in is analog. Although we call the world we live in a 'Digital World,' in reality, the 'Digit' itself is simply recorded on a certain analog machine.

Just because the 'AI' services we use today cause certain levels of error doesn't mean we can disregard their value as zero. Are Apple’s services flawless? (Vision Pro... I won’t say more.) Since humans are not perfect, everything created by humans can never be perfect. Between 0 and 1, there are countless values like 0.1, 0.0002, etc. Ignoring this concept is something I personally find truly repulsive.

When the so-called 'AI' industry was booming, Apple was completely fumbling. Why? Because Apple is not perfect either. After all, Apple is run by people.

"The end of tuning is stock."

https://news.ycombinator.com/item?id=41910736

Yes, I was a huge fan of Ultima 7, 9 and Online. I remember that incredible sense of freedom gave me a kind of liberation(?). It’s an honor to be able to have this conversation with you. Thinking about how you were already grappling with pathfinding issues and addressing them in real-time back then makes me feel a bit envious. I’m sure there weren’t many people who could have had such experiences at that time. It’s thanks to people like you with those experiences that today’s programming languages and skills have developed as they have. My technical level is far below yours, but I want to complete a lightweight pathfinding algorithm for my project, no matter what. Thank you for sharing such an inspiring story.

Oh, thank you. I'll have to take a look at the source code as well.

Oh~ This is very similar to the concept I was thinking of. I don't really like the idea of exploring strictly in a clockwise direction, though. Thank you for the information!

I’ve reviewed the source code. It seems like starting with clear and accurate information about the obstacles could be an issue. Also, if the obstacles become very large, preprocessing will likely be necessary.

Oh, I saw that blog too. It helped me a lot to be inspired. What I mean by "performance" is that I want to minimize preprocessing, and I want to minimize the amount of computation I can do even when I'm navigating in real time. I'll definitely watch the video you gave me. Thank you!

Yeah, I thought about that too, but I'm also trying to keep pre-processing work as light as possible.

The algorithm for finding detour points is as follows. In fact, I’ve improved it a bit through research:

1. Detect a collision with an obstacle on the straight path connecting the starting point and the destination. 2. Decide which direction to explore along the obstacle's outline (for now, the side closer to the destination). 3. If the end of the visible outline is reached, search for an appropriate detour point around that outline. 4. Select a detour point where a straight-line movement from the starting point avoids the obstacle, preferably closer to the destination.

---

If the first detour point selection fails, I plan to search in the *opposite direction* along the outline where the obstacle was first encountered. I’m currently working on resolving this part.

You can check out my progress here: https://github.com/Farer/bw_path_finding

Oh~ That’s awesome! I’ll start analyzing the source code! Thank you!

Oh! That’s exactly correct! It seems I didn’t explain it clearly enough.

As you mentioned, *"the goal is to find a decently short path, not necessarily the shortest one."* That’s absolutely right. The basic idea is that when an obstacle is encountered, *I just need to find the first detour point.* After that, the process can be repeated from that detour point in the same way.

The link you provided is also very intriguing. I’ll take a closer look and provide feedback again afterward!

Thank you so much for providing an example related to the project!

The example you mentioned might need to be delegated to the wolf’s *lifestyle logic*. For more thoughts on this, it would be great if you could check out the link below: https://blog.breathingworld.com/concept-meeting-for-wolf-dev...

In conclusion, the wolf will, of course, have intelligence and will also possess skills for hunting. With those capabilities, the wolf will likely be able to track the traces left by the rabbit and ultimately find it.

Yes, I’m also trying to explore as many options as possible. However, I do have a strong desire to minimize preprocessing as much as I can.

Oh, as expected, A* couldn't be fully utilized on older hardware. I can totally relate, as I’m running my server on a Mini PC with an *N100 CPU* right now.

Hearing stories about the challenges and solutions for low-spec hardware like this is incredibly fascinating.

A* and JPS seem a bit different from the direction I’m aiming for.

Wow~ You’re one of the developers of Ultima, a game I truly loved! The concept of using "highways" is really fascinating!

However, in my project, everything is in plain view for everyone to observe, so I won’t be able to use any cheats like that!

Oh~ This is definitely worth referencing as well. Thank you for the information!

Oh! This seems like something even AIs haven’t suggested before. The fact that it attempts paths in real-time without preprocessing is what I like the most! I definitely need to research this further! I’ll definitely take a look at it. Thank you!

@wormlord

Yes, as you mentioned, the fact that "it’s not guaranteed to always find a solution" is perfectly fine for me. That’s because it feels more natural.

Moreover, since my goal isn’t to always find an answer in the shortest time, this approach aligns even better with my intentions. In my case, I’d like to handle aspects like "trial and error" as part of the learning concept for entities such as rabbits or wolves.

And of course, I’m aiming for something that works well in *dynamic situations*, not just static ones.

@deathanatos

Yes, as you mentioned, the idea of "it doesn’t have to be the optimal path" aligns perfectly with my thinking as well.

In the case of the algorithm I’m currently working on, it wouldn’t enter those concave areas directly. Instead, it would "look" at the obstacle first, recognize that the path is blocked, and then proceed toward one of the corners at the bottom or top of the concave shape. Afterward, it should be able to exit again using the same approach.

However, to make it behave more like a creature with vision in certain situations, it might be good to enhance the algorithm slightly so that it can preemptively recognize "Ah, this is a concave obstacle." That way, it could avoid inefficient behavior while still maintaining its "realistic" navigation style.

I haven’t watched the video yet, but I really like the title: “on slow computers.” I'll give you feedback again after I watch it. The document you mentioned also seems to have a lot to learn from.

It would be great if it could be applied universally, but it seems that accommodating all situations in the real world won’t be easy.

In the end, I feel like it might have to transition into the realm of inference, much like AI that mimics human reasoning.

I also hope it works as well as you’re thinking.

@johnfn The approach I’m considering would be similar to how humans navigate: using only visible information to continuously infer and find the way in real-time.

It would essentially break down the flow of how humans navigate into small, incremental steps. Look with their eyes, make a judgment, move, and repeat the process again and again...

Of course, trial and error could also occur. This might actually make it feel more natural.

As far as I’ve researched, if there’s an assumption that there are no obstacles, the fastest way to select a straight path is Bresenham's Line Algorithm. If I’m mistaken about this, please let me know!

In my project, since I don’t need to guarantee complete real-time processing, there isn’t an absolute necessity to find paths as quickly as possible. However, since many entities need to find paths simultaneously, I’d like to keep the computations as minimal as possible.

It might be similar to what you mentioned about algorithms being fast enough on low-spec hardware. In my case, I’m currently using an ultra-low-power Mini PC with an *N100 CPU* as a server. This choice not only helps me study methods to optimize performance but also satisfies my curiosity about fully leveraging the advantages of *MSA (Microservice Architecture)*-based services.

First, I understand that the JPA (Jump Point Search) family only works efficiently in static environments. This means it requires preprocessing to achieve high efficiency.

What I'm aiming for, however, is a real-time scenario where such preprocessing is not strictly necessary. I want to implement something akin to how many creatures with human-like vision navigate using only partial information, just as humans do in real-life situations.

Currently, trees are appearing and disappearing dynamically. In the future, such situations are expected to occur more frequently, so I am aiming to create a lightweight solution that can handle these changes in real-time.

As you mentioned, for cases like rabbits, their location information is already preprocessed and divided by zones. Since this is a small task, it doesn't impose a significant burden on the system. This information is intended to be used when wolves are searching for rabbits.

Additionally, I have recently been considering processing even smaller zones than the current ones to handle the vision of wolves more effectively.

Oh! This is it! This is exactly why I wanted to create a new algorithm!

@jvanderbot

Ah, I did hear about the Visibility Graph through AI. I didn’t fully understand it due to my lack of knowledge. But with you bringing it up again, I think I should look into that as well. Thank you for your kind response.

I think this part also needs to be considered. Many pathfinding algorithms, including A* , aim to find the optimal path. However, my goal started with replicating how humans visually find their way.

In such cases, humans cannot see the back side of obstacles. Additionally, there are situations where the exact destination may not be known. They simply infer based on what they can see in front of them. "There's an obstacle over there. Which way would be better to go around?" My approach began from this perspective.

This flow of pathfinding is entirely different from A*. So, the algorithm has been modified a bit now. I changed it so that it does not investigate the entire shape or full outline of obstacles. The flow is as follows:

1. Attempt to move in a straight line in the direction I want to go. 2. Detect an obstacle. 3. Explore the visible outline of the obstacle, focusing on the side that seems closer to the destination. 4. When reaching the endpoint of the outline, select an appropriate detour point nearby.

The final detour point will, of course, be a location where a straight-line movement from the starting point avoids hitting the obstacle. Once I reach the detour point from the starting point, I repeat the process.