PROSPECTS OF USING THE WAVE FUNCTION COLLAPSE ALGORITHM FOR IMPROVING HEURISTIC SEARCH STRATEGIES

Denys-Roman Rudyk, Oleksii Kushnir

Abstract


Background. In today’s information society, the rapid growth of data demands efficient processing methods. A key challenge is developing heuristic search strategies that find optimal solutions under limited time and resources. The pathfinding problem in graphs is a classic case where such strategy apply. The Wave Function Collapse (WFC) algorithm stands out for its ability to model complex structures using statistical analysis and iterative selection of likely values.

Materials and Methods. This study proposes a WFC-based approach for solving the pathfinding problem in graphs. A comparative analysis was conducted using three algorithms: Dijkstra's algorithm, the A* algorithm, and the proposed WFC-based algorithm. Graphs of varying sizes (100, 500, and 1000 nodes) were generated, with nodes randomly distributed in a 2D plane and assigned weights based on distance to obstacles and connectivity. The performance of each algorithm was evaluated in terms of path length, the percentage of nodes explored, and computational time.

Results and Discussion. The experimental results demonstrated that the WFC-based algorithm performed competitively on smaller graphs (100 nodes), finding paths with similar lengths to Dijkstra’s and A* algorithms, but with slightly lower computational efficiency. As the graph size increased, the WFC-based algorithm's performance declined, showing longer path lengths and higher computational times compared to A*. Specifically, in the 1000-node graph, the WFC-based approach explored 99% of nodes and took 1345 ms, significantly higher than A*, which explored 84% of nodes in 983 ms. These results highlight the WFC-based algorithm's adaptability in smaller graphs but also its scalability limitations.

Conclusion. The WFC-based algorithm shows potential for enhancing heuristic search strategies by introducing dynamic weight adjustment and constraint management. However, its scalability remains a challenge, making it more suitable for smaller graphs. Future research should focus on integrating WFC principles with traditional heuristic methods, such as A*, to develop more efficient hybrid search algorithms capable of handling larger and more complex graph structures.

Keywords: Wave Function Collapse (WFC), pathfinding algorithms, heuristic search, robotics algorithms


Full Text:

PDF

References


  1. Zhao, P., & Guo, H. (2014). Scientific big data and digital Earth. Chinese Science Bulletin, 59(12), 1047–1054. https://doi.org/10.1360/972013-1054
  2. Xu, Y. (2024). The comparison of advanced algorithms for pathfinding robots. AIP Conference Proceedings, 3194(1), 020012. https://doi.org/10.1063/5.0223914
  3. Felner, A., & Stern, R. (2006). Heuristic Search. In F. Rossi, P. van Beek, & T. Walsh (Eds.), Handbook of Constraint Programming (pp. 579–623). Elsevier.
  4. Karth, I., & Smith, A. M. (2017). WaveFunctionCollapse is constraint solving in the wild. In Proceedings of the 12th International Conference on the Foundations of Digital Games (FDG).
  5. Mac, A., & Perkins, D. (2021). Wave function collapse coloring: A new heuristic for fast vertex coloring. arXiv:2108.09329. https://doi.org/10.48550/arXiv.2108.09329
  6. Kim, H., Lee, S.-T., Lee, H., Hahn, T., & Kang, S.-J. (2019). Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm. 2019 IEEE Conference on Games (CoG), 1–4. https://doi.org/10.1109/cig.2019.8848019
  7. Gumin, M. (2016). Wave Function Collapse. GitHub. Retrieved from https://github.com/mxgmn/WaveFunctionCollapse
  8. Newgas, A. (2021). Tessera: A Practical System for Extended Wave Function Collapse. In Proceedings of the 16th International Conference on the Foundations of Digital Games (FDG '21). Association for Computing Machinery. https://doi.org/10.1145/3472538.3472605




DOI: http://dx.doi.org/10.30970/eli.31.10

Refbacks

  • There are currently no refbacks.