This is a small project, visualizing simple implementation of MAPF by creating large state graph. It was done as a semestral project in Artificial Intelligence at my university.
- It generates all the possible state space with the possible configurations of the agents and creates a graph based on that.
- Then, uses A* on the state space graph to find better path based on Manhattan Distance on Heuristics and my custom G function for the "shortest" distance.
![Screen Shot 2023-05-16 at 17 27 13](https://private-user-images.githubusercontent.com/68243292/238694547-4c6869d9-b805-4a5e-b47b-c2719fb7bbe9.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MjYwOTc2MDUsIm5iZiI6MTcyNjA5NzMwNSwicGF0aCI6Ii82ODI0MzI5Mi8yMzg2OTQ1NDctNGM2ODY5ZDktYjgwNS00YTVlLWI0N2ItYzI3MTlmYjdiYmU5LnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA5MTElMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwOTExVDIzMjgyNVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTc5YmNlYjg1OTk3YTE4ZGMwNTNjZWZlYThkYjJhYWJiNzA5OGI3NTc1OGNhNGVlYjA3MjcwMDZjMWIwYmJhYWYmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.BU_qEUn0cZGzaLWsI5vVvu1uifWr5YbUu3Y4P6o2DO8)
Simply clone this repo and install pygame library. Required: Python3, Pygame.
maps/ - contains simple test maps. They are configurable at init(filename) call at main.py.
pathfinding.py - util functions that handles parsing, A* algorithm, generation of state space.
main.py - the program to run. Scroll to the bottom and change the maps in init function.