2 ms·

Do you mean an AST?

chrisseaton 6y ago
AST, CST, CFG, DFG, PDG, or any other data structure for representing a program. But I can't imagine it being done with a simple array or a hash map. The all end in T or G! How would you approach that with your way of doing things? I guess if you work on game engines this is a relevant problem? Or if not maybe a graphics data structure like a BSP? How do you do that without trees? Or a NPC navigation data structure? How do you do that without graphs?
- stephc_int13 6y ago
  BSP is a pretty outdated algorithm in the game engine space. I very often use spatial hashing instead of quad-trees or octrees. I rarely write interpreters but from memory a simple stack can go a long way. Scenes are stored as flat arrays of components (ECS style) Navigation (path finding) is very dependent on the internal level architecture, many tricks can be used to avoid trees or complex computations.
  - codetrotter 6y ago
    Just wanted to say thank you for this comment. It led me to this paper http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf which introduced some new ideas to me alongside of concepts that I were familiar with so it’s been generally easy but useful reading so far :)
  - chrisseaton 6y ago
    You probably know more than me but I don't really get how you can go from text source code to a stack without going through a tree or with recursion!
    - stephc_int13 6y ago
      https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
- stephc_int13 6y ago
  I suggest watching this excellent talk on Data Oriented Design from Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
  - chrisseaton 6y ago
    I've watched this talk before, and I really think it's just about transposition. Column rather than row. If you have a graph and represent it as an adjacency array... lol it's still a graph you're just looking at it differently! You haven't gotten rid of the inherent graph property of the data structure!

Do you mean an AST?

AST, CST, CFG, DFG, PDG, or any other data structure for representing a program. But I can't imagine it being done with a simple array or a hash map. The all end in T or G! How would you approach that with your way of doing things? I guess if you work on game engines this is a relevant problem? Or if not maybe a graphics data structure like a BSP? How do you do that without trees? Or a NPC navigation data structure? How do you do that without graphs?

stephc_int13 6y ago
BSP is a pretty outdated algorithm in the game engine space. I very often use spatial hashing instead of quad-trees or octrees. I rarely write interpreters but from memory a simple stack can go a long way. Scenes are stored as flat arrays of components (ECS style) Navigation (path finding) is very dependent on the internal level architecture, many tricks can be used to avoid trees or complex computations.
- codetrotter 6y ago
  Just wanted to say thank you for this comment. It led me to this paper http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf http://www.cs.ucf.edu/~jmesit/publications/scsc%202005.pdf which introduced some new ideas to me alongside of concepts that I were familiar with so it’s been generally easy but useful reading so far :)
- chrisseaton 6y ago
  You probably know more than me but I don't really get how you can go from text source code to a stack without going through a tree or with recursion!
  - stephc_int13 6y ago
    https://en.wikipedia.org/wiki/Shunting-yard_algorithm https://en.wikipedia.org/wiki/Shunting-yard_algorithm
stephc_int13 6y ago
I suggest watching this excellent talk on Data Oriented Design from Mike Acton: https://www.youtube.com/watch?v=rX0ItVEVjHc https://www.youtube.com/watch?v=rX0ItVEVjHc
- chrisseaton 6y ago
  I've watched this talk before, and I really think it's just about transposition. Column rather than row. If you have a graph and represent it as an adjacency array... lol it's still a graph you're just looking at it differently! You haven't gotten rid of the inherent graph property of the data structure!