Proposal/Ideas of things to add
IanDoarn opened this issue · 23 comments
Proposals / Ideas
'bad title'
I'd like to propose some things that should be added to this! I'm by no means advanced enough to understand some things here (stacks, heaps, A-star), but I definitely thing we should expand to even more examples as well as other things!
Please read this and let me know if any seem like good/bad ideas!!
Data Structures
- Hash Maps / Hash Tables
- Binary Heap
- Matrix
Math
- Factorial
- PI
- Summation
- Sequences?
- Common formulas: Quadratic, slope, distance, ect.
- Binary Conversion: bin to hex, bin to ascii, ascii to hex, ect
- Union
- Partition
Geometry
- Collision detecion
- Euclidean Distance
- Triangluation
- Maxmimum Area
Others
- Physics?
- Iteration
These are just some idea's I;ve have had, feel free to let me know if this is anything interesting!
Seems great. These ideas are surely great. We will try to implement each possible algorithm. Thank you!
Feel free to place these in TODO.md
I can definitely help with the collision detection algorithms and arcade physics (for the complicated physics Box2D is pretty legible).
Other things I was going to work on first was:
- Bidirectional A* - it's very rarely worth it to use bidirectional algorithms but having one in there can be helpful
- Concave polygons. These will be placeable on the grid and are necessary to test the quadtree
- Quadtree Grid
- Figure out a way to make the A* algorithms also work on the grid, or make a version that works on the grid, since that's probably a more common usecase than on graphs because its much more memory efficient
- Visualizer? Graphical visualizer would probably be too intense for python but I would be willing to make a C# library that binds with the python via ironpython for visualizing these. Alternatively could just delegate to http://qiao.github.io/PathFinding.js/visual/ (though it is missing some of the fancier algorithms)
- Theta * (this only works on certain types of grids things)
- Lazy Theta * - probably best algorithm to use for 2D games
- Jump point search - this algorithm is nearly useless in practice (only uniform grids with point-particle entities) but is pretty neat to watch
- D* (both variants) - these two algorithms are strictly worse than D* Lite but provide historical context
- D* Lite - best algorithm for robots on a flat plane (or at least where you can ignore elevation)
@Tjstretchalot a visualizer would be nice but what about users on Mac? And there are libriaries for visualizing in python, at least i think. A better option would be to build a module in C++/C which I could probably whip up!
@Tjstretchalot @IanDoarn I can help with Math implementations. I have some pseudo codes available for the same.
@IanDoarn I was thinking IronPython with Mono which is cross-platform. I'm not sure if you've tried the python GUI libraries but they are pretty terrible. They aren't even particularly pythonic, so there's no language advantage there. Going from Python to C++/C seems like an overkill jump where C# would suffice fine, but if you want to do that than binding with Cython will work.
In my opinion we shouldn't do anything graphics related actually in python - it's not where python shines :)
@OmkarPathak I won't be messing with those (at least for a while) so if you do you won't see any merge errors/duplicated work from me!
@Tjstretchalot Oh I know they are aweful. Maybe the visualizer should wait for awhile, and prioritize the main focus of Pygorithms first?
But by all means I'd love to see what you could make!
@IanDoarn Yeah perhaps it should wait. It can be hard to understand the difference between some of the algorithms without a visualizer, especially the ones with very few open-source implementations (when I google "Theta* python" no relevant links come up) but it does clutter the repo.
@OmkarPathak @IanDoarn When you make the binary heap add a search function (it's not in the heapq implementation). It's technically the same worst case performance but should beat average case performance over a linear search because it will be able to skip subtrees. Alternatively, adding it to the current heap implementation would work as well
@Tjstretchalot @OmkarPathak I can work on basic binary conversions between bases
How about algorithms like 0/1 Knapsack and Greedy Knapsack?
I can help with it, if it is worth adding.
@sharadbhat you can help with greedy knapsack. I am halfway on 0/1 knapsack
@OmkarPathak I'll get started on it.
@IanDoarn can you add some tests for binary conversion?
@OmkarPathak I can
#61 is relevant to this thread
@OmkarPathak I can help in in implementing leaf count algo in tree/data structures.
@utkarshyadavin that would really be great. Go on. I am waiting for the PR
How about calculating cubic equation?
@IanDoarn @OmkarPathak Can we add Project Euler problems in python.
Find the time taken to process the algorithm?
@SaashaJoshi idea seems good. But the problem is each algorithm would take different timestamps to execute depending on the underlying hardware. Also, there are many modules like timeit which are specifically made for calculating execution time. If you still feel that we should include time taken to process the algo, open a PR and we would think about it 😄
@OmkarPathak the time taken would definitely depend on the hardware but maybe we can further generalize an algorithm which can compare the efficiency of different computer hardware or in specific the processors in the field of data science or more elaborately machine / deep learning.
PS: I'm new to such topic of discussion but i'll surely open a PR!