Patrzę na ten problem od kilku dni. Przygotowałem tę grafikę, aby pomóc mi w wizualizacji problemu: (z wykresu wiemy, że linia przecina [1, 1], [1, 2], [2, 2], [2, 3], kończąc na [ 3,3])
Chcę przejść wzdłuż linii do każdej przestrzeni siatki i sprawdzić, czy materiał przestrzeni siatki jest solidny. Wydaje mi się, że już znam matematykę, ale nie byłem jeszcze w stanie jej połączyć. Używam tego do testowania linii wzroku i eliminowania węzłów po znalezieniu ścieżki za pomocą moich algorytmów odnajdywania ścieżek - moi agenci nie widzą stałego bloku, dlatego nie mogą przejść przez jeden, dlatego węzeł nie jest eliminowany ze ścieżki, ponieważ jest wymagany do nawigacji w rogu.
Potrzebuję więc algorytmu, który będzie przechodził wzdłuż linii do każdej przecinającej się przestrzeni siatki. Jakieś pomysły?
Przyjrzałem się wielu powszechnym algorytmom, takim jak Bresenham, i takim, który kroczy w określonych odstępach czasu wzdłuż linii (niestety ta metoda pomija kafelki, jeśli przecinają one mniejszy klin niż rozmiar kroku).
Zapełniam teraz moją tablicę masą funkcji floor () i ceil () - ale robi się to zbyt skomplikowane i obawiam się, że może to spowodować spowolnienie.