search

chiyadev / genshin-schedule

🕑 Genshin farming scheduler
https://genshin.chiya.dev
MIT License
72 stars 17 forks source link

Efficient route generation for tasks #23

Open luaneko opened 3 years ago

luaneko commented 3 years ago

Currently the task list is naively sorted such that more overdue tasks appear first. If a pathfinding algorithm for tasks is to be implemented, it could potentially make farming more time efficient. Unfortunately this is an instance of TSP which is an NP-hard problem.

I tried implementing the simulated annealing algorithm but ended up with a big mess. Maybe it was not a suitable algorithm for this problem. Opening this issue to see if anyone is interested in tackling this.

Successful initial implementation must account for teleports as weight=0 unidirectionally. Elevation and water consideration is an added bonus (there are no geo data for these though).

RaffaeleAmmirati commented 3 years ago

I had read the wiki on the merchant problem and if you can resolve it and make it in the site it will be awesome. But instead of making things complicated, I have maybe a simple idea. I known nothing of database and programming so sorry if I ask something that is not possible or worse that the actual state. Every gamer have their route with they are familiar. So instead of the above solution of the perfect route, why we don't do it how "Pozolo" suggested in the "Possible improvements on Today's Task and Map" issue?

The image I made is a possible way of how to implement the solution of "Pozolo" Route Task We can mark a task as parent, and the other task if marked as child can select ONLY the task marked as parent. Sorry for my english and thank you for your work.