AlexStv
|
|
« Reply #3020 on: November 30, 2012, 08:58:49 AM » |
|
This means that A*'s open and closed lists expand towards the goal and start to skip back to alternatives as that growth meets dead ends. This behaviour occurs because of the relationship between the open and closed lists.
The skipping back is what I was referring to as backtracking, I suppose it wasn't technically A* until that was added.
|
|
|
Logged
|
|
|
|
Geti
|
|
« Reply #3021 on: December 01, 2012, 06:25:49 PM » |
|
The skipping back is what I was referring to as backtracking, I suppose it wasn't technically A* until that was added.
No, it likely just isn't A*. Do you have a list of open/closed nodes (or some in-place way of determining closedness, though that rules out running 2 searches at the same time)? Do you have some function for determining the minimum distance from some point to your goal?. Because you need those to implement A*. You need your open list so you can find the open node closest to the goal and try from there (-> no "dead end" issue). you need the closed list so you don't revisit old nodes. you need the function so you know which nodes are closer.
|
|
|
Logged
|
|
|
|
AlexStv
|
|
« Reply #3022 on: December 02, 2012, 05:56:03 AM » |
|
The skipping back is what I was referring to as backtracking, I suppose it wasn't technically A* until that was added.
No, it likely just isn't A*. Do you have a list of open/closed nodes (or some in-place way of determining closedness, though that rules out running 2 searches at the same time)? Do you have some function for determining the minimum distance from some point to your goal?. Because you need those to implement A*. You need your open list so you can find the open node closest to the goal and try from there (-> no "dead end" issue). you need the closed list so you don't revisit old nodes. you need the function so you know which nodes are closer. Yes and yes, Open and closed arrays and it finds nodes from the open list based on distance to the node from the parent plus distance from the node to the target. With just these two elements it is possible for the path to lead down a dead end, then because of the closed list not be able to find any open nodes (or tiles) to find its way back out unless you have a way to go back and "undo" the path down the dead end. This is my first time implementing A* so it's very possible I've over looked something but I can't see it at all, here is what I'm thinking of as a dead end: http://i.imgur.com/wSca8.png and that's why the script needed to have an element to undo the last node and try again but with the last node on the closed list.
|
|
|
Logged
|
|
|
|
AbsoluteZero2A03
TIGBaby
|
|
« Reply #3023 on: December 02, 2012, 06:05:30 AM » |
|
This is a good thread to post my first post.
I've been programming for just over a year now, starting with Python. I started programming some game stuff with Lua and LOVE2D, and now I'm working with C++ with SFML.
I'm actually accomplishing things and it feels great.
|
|
|
Logged
|
|
|
|
Vithium
Level 1
|
|
« Reply #3024 on: December 02, 2012, 07:48:23 AM » |
|
I have my tile map tool software near completion. That makes me very happy. It has a full layer system to have tile layers, doodad(object) layers, a tile editor built in, project organization, and even working on a physic layer which will just be a layer to graphically draw areas that represent something that can be collided into. This can then be output into a data file that can be imported into the game to be used by something like Box2D. Pretty excited bout it but not finished, just got most of it done I would say.
|
|
|
Logged
|
|
|
|
ThemsAllTook
|
|
« Reply #3025 on: December 02, 2012, 10:21:57 AM » |
|
Yes and yes, Open and closed arrays and it finds nodes from the open list based on distance to the node from the parent plus distance from the node to the target. With just these two elements it is possible for the path to lead down a dead end, then because of the closed list not be able to find any open nodes (or tiles) to find its way back out unless you have a way to go back and "undo" the path down the dead end. This is my first time implementing A* so it's very possible I've over looked something but I can't see it at all, here is what I'm thinking of as a dead end: http://i.imgur.com/wSca8.png and that's why the script needed to have an element to undo the last node and try again but with the last node on the closed list. If I'm remembering my A* correctly, you'd want to leave the tile just below the starting position on the open list the entire time you're investigating the dead end. It would get added on the first step along with the tile immediately to the right, but kept at a lower priority because it's farther from the destination, so the entire dead end path would be investigated before coming back to it. Once you hit the wall, it's the most appealing option in your open tile list, so it's investigated next. This animation from Wikipedia is pretty useful in seeing A* behavior:
|
|
|
Logged
|
|
|
|
RalenHlaalo
|
|
« Reply #3026 on: December 07, 2012, 07:39:30 PM » |
|
My engine is coming along nicely. Check out this beautiful rotating square! It rotates at 180 degrees per second, and can be toggled on-off. The render loop runs at 60fps, and the main loop at around 5 million fps. When the window is resized, the view is scaled accordingly. And all this in less than 100 lines of code. Damn, I love this square so much.
|
|
« Last Edit: December 08, 2012, 10:29:34 AM by RobJinman »
|
Logged
|
|
|
|
RalenHlaalo
|
|
« Reply #3027 on: December 08, 2012, 10:21:54 AM » |
|
My engine is coming along nicely. Check out this beautiful rotating square! It rotates at 180 degrees per second, and can be toggled on-off. The render loop runs at 60fps, and the main loop at around 5 million fps. When the window is resized, the view is scaled accordingly. And all this in less than 100 lines of code. Damn, I love this square so much. I think I need to lay off the caffeine for a while These 4am coding sessions make me go slightly mad.
|
|
|
Logged
|
|
|
|
kamac
|
|
« Reply #3028 on: December 08, 2012, 10:27:41 AM » |
|
I think I need to lay off the caffeine for a while These 4am coding sessions make me go slightly mad. Why? That's a glorious square indeed.
|
|
|
Logged
|
|
|
|
Sergi
|
|
« Reply #3029 on: December 08, 2012, 02:26:58 PM » |
|
I think I need to lay off the caffeine for a while These 4am coding sessions make me go slightly mad. Why? That's a glorious square indeed. Meh. Squares are overrated. (I just played some Fez )
|
|
|
Logged
|
|
|
|
SodiumEyes
|
|
« Reply #3030 on: December 08, 2012, 10:56:23 PM » |
|
Implemented a class for mesh silhouette rendering using an edge buffer. You just need to update it every time the camera or object changes, and it builds a index array for the vertex position buffer used to render the mesh itself.
|
|
|
Logged
|
|
|
|
Azure Lazuline
|
|
« Reply #3031 on: December 09, 2012, 11:45:07 AM » |
|
Is the whole game going to look like that? I hope so.
|
|
|
Logged
|
|
|
|
kamac
|
|
« Reply #3032 on: December 09, 2012, 12:07:30 PM » |
|
That's nifty, SodiumEyes. I just checked my current game code. It's 3970 lines, and I haven't even got the editor done (would've been more, but I am using a library for that handles all the low level stuff, including IO and so on)
|
|
|
Logged
|
|
|
|
RalenHlaalo
|
|
« Reply #3033 on: December 09, 2012, 12:26:40 PM » |
|
My 2d engine is 13k lines so far, and I haven't built the editor yet
|
|
|
Logged
|
|
|
|
Belimoth
|
|
« Reply #3034 on: December 09, 2012, 12:52:28 PM » |
|
Haha, I hope you guys never need to port your shit.
|
|
|
Logged
|
|
|
|
RalenHlaalo
|
|
« Reply #3035 on: December 09, 2012, 01:19:27 PM » |
|
Haha, I hope you guys never need to port your shit.
My engine is actually very portable, and that's partly the reason for its large size.. all the abstraction layers, etc. I have different low-level modules for each platform, all with identical interfaces, however some platforms can share the same implementation of some things -- e.g. both Linux and Windows can use the OGLES2.0 renderer. The rest of the engine code is shielded from the underlying rendering technology, and the same is true for XML parsing, physics, window/io stuff, and so on.
|
|
|
Logged
|
|
|
|
rivon
|
|
« Reply #3036 on: December 09, 2012, 02:13:05 PM » |
|
I just checked my current game code. It's 3970 lines, and I haven't even got the editor done You're lucky. 3970 is nothing. My last C++ project has about 11k lines of code and there's almost nothing done (mostly just engine stuff) and I'm using SDL, no OpenGL.
|
|
|
Logged
|
|
|
|
Geti
|
|
« Reply #3037 on: December 09, 2012, 02:45:50 PM » |
|
KAG classic is >200k lines of C++ on top of irrlicht and ENet. My largest project before working on KAG barely pushed 20k lines. Size is relative.
Found a way to optimise water to the point where dynamic water over net might not give everyone cancer. 10byte 8x8 chunk updates (2 bytes for chunk position, 64 bits for the data) with an old state or 2 stored for animation + autotiling with the tilemap, should be legit.
|
|
|
Logged
|
|
|
|
Graham-
|
|
« Reply #3038 on: December 11, 2012, 04:27:54 PM » |
|
I just implemented a breadth-first-search! I learned that shit in school!
|
|
|
Logged
|
|
|
|
_Tommo_
|
|
« Reply #3039 on: December 11, 2012, 07:16:23 PM » |
|
I made sound creation amortized O(1) The search for a free OpenAL source was for some reason O(n) as for each new sound, all the source pool was scanned for a new source. Now I've added a busy list + a idle stack, so I can just pop the stack to get an idle source. It is "amortized" because once the stack is depleted, I run a O(n) search to add back all the stopped sources to the free stack. It brought no kind of performance improvement whatsoever but it feels good and tidy
|
|
|
Logged
|
|
|
|
|